Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define maxm 100001
- #define pb push_back
- using namespace std;
- // Similar to finding k-core graphs
- // Input:
- // 9 17 3
- // 1 2
- // 1 3
- // 2 3
- // 2 6
- // 3 4
- // 3 5
- // 3 6
- // 3 7
- // 4 5
- // 4 7
- // 4 8
- // 5 7
- // 5 8
- // 6 7
- // 6 9
- // 7 8
- // 7 9
- // Output:
- // 5
- // Input:
- // 13 12 3
- // 1 2
- // 1 3
- // 1 4
- // 2 5
- // 2 6
- // 2 7
- // 3 8
- // 3 9
- // 3 10
- // 4 11
- // 4 12
- // 4 13
- // Output:
- // 0
- int N, M, K, u, v, c;
- vector<int> deg(maxm), g[maxm];
- int main(){
- cin>>N>>M>>K;
- for(int i=0; i<M; ++i){
- cin>>u>>v;
- g[u].pb(v);
- g[v].pb(u);
- deg[u]++;
- deg[v]++;
- }
- queue<int> q;
- for(int i=1; i<=N; ++i)
- if(deg[i] > 0 && deg[i] < K)
- q.push(i);
- while(!q.empty()){
- int x = q.front();
- q.pop();
- deg[x] = -1;
- for(int i=0; i<g[x].size(); ++i){
- deg[g[x][i]]--;
- if(deg[g[x][i]] > 0 && deg[g[x][i]] < K)
- q.push(g[x][i]);
- }
- }
- for(int i=1; i<=N; ++i)
- if(deg[i] >= K)
- c++;
- cout<<c<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement