Cod sursa(job #547351)

Utilizator stefynr8Space Monkey stefynr8 Data 6 martie 2011 11:51:00
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>
#include <vector>

using namespace std;

vector <int> a[100005];


int n,m,viz[100005],h,x,y;


void DFS(int nod)
{
	int i;
	viz[nod] = 1;
	for (i = 0; i < a[nod].size(); i++)
        if (!viz[a[nod][i]]) DFS(a[nod][i]);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);

	int i;

	for (i=1;i<=m;i++)
	{
	 scanf("%d %d",&x,&y);
     a[x].push_back(y);
	}


	for (i=1;i<=n;i++) if (!viz[i]) {
                                     h++;
                                     DFS(i);
                                     }

	printf("%d\n",h);
	return 0;
}