Cod sursa(job #1167269)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 4 aprilie 2014 18:27:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<cstdio>
#include<vector>
using namespace std;
const int N=100000;
vector<int>g[N+1];
bool vis[N+1];
int n,m;
void scan(){
    int i,v1,v2;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&v1,&v2);
        g[v1].push_back(v2);
        g[v2].push_back(v1);
    }
}
void init(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scan();
}
void dfs(int father){
    int i,son;
    vis[father]=true;
    for(i=0;i<g[father].size();i++){
        son=g[father][i];
        if(!vis[son])
            dfs(son);
    }
}
int main(){
    int i,res=0;
    init();
    for(i=1;i<=n;i++)
        if(!vis[i]){
            res++;
            dfs(i);
        }
    printf("%d",res);
    return 0;
}