Cod sursa(job #671472)

Utilizator OanaCristinaFlorescu Oana Cristina OanaCristina Data 31 ianuarie 2012 15:49:04
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.45 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");

int A[2000][2000],S[2000],n,cc,m;

void df(int nod)
{
	int i;
	for(i=1;i<=n;i++)
		if(A[nod][i] && S[i]==0)
		{
			S[i]=cc;
			df(i);
		}
}

int main()
{
	int i,x,y;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>x>>y;
		A[x][y]=A[y][x]=1;
	}
	for(i=1;i<=n;i++)
		if(S[i]==0)
		{
			cc++;
			df(i);
		}
	out<<cc;
	return 0;
}