Cod sursa(job #633338)

Utilizator andumMorie Daniel Alexandru andum Data 13 noiembrie 2011 16:27:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 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++;
				  S.push(i);
				  while (!S.empty())
				  {
					  k=S.top();
					  v[k]=1;
					  for (j=1; j<=a[k][0]; ++j)
						  if (!v[a[k][j]])
						  {
							  S.push(a[k][j]);
							  break;
						  }
						  
					  if (j==a[k][0]+1)
						  S.pop();
				  }
				  
           }
    printf("%d", nc);
    return 0;
}