Cod sursa(job #633332)

Utilizator andumMorie Daniel Alexandru andum Data 13 noiembrie 2011 16:19:30
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include <stack>

using namespace std;

int n,m,x,y,a[100001][25],p,nc,vb,v[100001],i,k,j;
stack <int> S;

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][0]++;
             a[x][a[x][0]]=y;
             a[y][0]++;
             a[y][a[y][0]]=x;
        }     
    for (i=1;i<=n;i++)
        if (!v[i])
           {
                  nc++;
				  while (!S.empty())
					  S.pop();
				  S.push(i);
				  while (!S.empty())
				  {
					  k=S.pop();
					  for (j=1; j<=a[k][0]; ++j)
						  if (!v[a[k][j])
							  S.push(a[k][j]);
				  }
				  
           }
    printf("%d", nc);
    return 0;
}