Cod sursa(job #1441284)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 24 mai 2015 01:12:13
Problema Parcurgere DFS - componente conexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>
#include<vector>
using namespace std;
int vc[100001],nr=0;
vector<vector<int> > v(100001);
void dfs(int nod){
    int a=v[nod].size(),i;
    vc[nod]=1;
    for(i=0;i<a;i++)
        if(vc[v[nod][i]]==0)
            dfs(v[nod][i]);
}
int main(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int n,m,i,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(i=1;i<=n;i++)
        if(vc[i]==0){
            nr++;
            dfs(i);
        }
    printf("%d",nr);
	return 0;
}