Cod sursa(job #1810659)

Utilizator vladisimovlad coneschi vladisimo Data 20 noiembrie 2016 13:51:48
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int c[100001],n,m,r,p,u;
bool a[10001][10001],v[100001];
void latime(int r){
    int i,k;
    p=1;
    u=1;
    c[u]=r;
    v[r]=1;
    while(p<=u){
        k=c[p];
        for(i=1;i<=n;i++)
            if(a[k][i]==1&&v[i]==0){
                u++;
                c[u]=i;
                v[i]=1;
            }
        p++;
    }
}
int main()
{
    fin>>n>>m;
    int k,i,j;
    for(k=1;k<=m;k++){
        fin>>i>>j;
        a[i][j]=1;
        if(i==j)
            a[i][j]=0;
    }
    int nrc=0;
    for(i=1;i<=n;i++)
        if(v[i]==0){
            nrc++;
            latime(i);
        }
    fout<<nrc;
    return 0;
}