Cod sursa(job #2001637)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 17 iulie 2017 12:35:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
#include<vector>
using namespace std;
const int NMAX=100005;
int t[NMAX],d[NMAX],f[NMAX];
bool viz[NMAX];
vector <int> G[NMAX];
int n,time;
void DFS(int u){
    viz[u]=1;
    time++;
    d[u]=time;
    for(int j=0;j<G[u].size();j++){
        int v=G[u][j];
        if(!viz[v]){
            t[v]=u;
            DFS(v);
        }
    }
    time++;
    f[u]=time;
}
int main(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int m;
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int sol=0;
    for(int i=1;i<=n;i++)
        if(!viz[i]){
            sol++;
            DFS(i);
        }
    printf("%d", sol);
    return 0;
}