Cod sursa(job #2145804)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 27 februarie 2018 17:05:04
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include<vector>
#define N 100001
#include<deque>

using namespace std;

int n,m,s;
vector<int> graph[N];
bool check[N];
int ans=0;
deque<int> q;

int main(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<m;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i=1;i<=n;++i)
        if(!check[i]){
            ans+=1;
            check[i]=1;
            q.push_back(i);
            while(q.size()>0){
                int t = q.front();
                q.pop_front();
                for(int i=0;i<graph[t].size();++i){
                    int node = graph[t][i];
                    if(check[node])continue;
                    check[node]=1;
                    q.push_front(node);
                }
        }


    }
    printf("%d",ans);
}