Mai intai trebuie sa te autentifici.
Cod sursa(job #361298)
Utilizator | Data | 4 noiembrie 2009 16:08:02 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include<stdio.h>
#include<vector>
#define max 100001
#define pb push_back
using namespace std;
vector< vector<int> > a(max);
short v[max];
int n,m,nr,k;
void data(){
FILE *f=fopen("dfs.in","r");
int x,y;
fscanf(f,"%d%d",&n,&m);
for(; m-- ;){
fscanf(f,"%d%d",&x,&y);
a[x].pb(y);
a[y].pb(x);
}
}
void dfs(int nod){
int i;
v[nod]=1;
for(i=0; i<a[nod].size(); i++)
if( !v[a[ nod ][ i ]] ) dfs( a[ nod ][ i ] );
}
int main(){
FILE *g=fopen("dfs.out","w");
data();
int i;
for(i=1;i<=n;i++)
if(!v[i]) {nr++;dfs(i);}
fprintf(g,"%d",nr);
return 0;
}