Cod sursa(job #547372)

Utilizator stefynr8Space Monkey stefynr8 Data 6 martie 2011 12:01:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>

using namespace std;

vector <int> a[100005];


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


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

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






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

    y=1;
    do
    {
        ok=0;
        for (i=y;i<=n;++i)
            if (viz[i]==0)
            {
                ok=1; y=i; break;
            }
        if (ok) { h++; DFS(i);}
    }while(ok);
//	for (i=1;i<=n;i++) if (!viz[i]) {
//                                     h++;
//                                     DFS(i);
//                                     }

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