Cod sursa(job #1674889)

Utilizator CrystyAngelDinu Cristian CrystyAngel Data 4 aprilie 2016 22:11:17
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;
vector <int> v[100010];
bitset <100010> w;
void df(int x)
{
    int i;
    for(i=0; i<v[x].size(); ++i)
        if(!w[v[x][i]])
            df(v[x][i]);
    w[x]=1;
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int n,m,a,b,i,N=0;
    scanf("%d%d",&n,&m);
    for(i=0; i<m; ++i)
    {
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
    }
    for(i=1; i<=n; ++i)
        if(!w[i])
        {
            ++N;
            df(i);
        }
    printf("%d",N);
}