Cod sursa(job #632444)

Utilizator yamahaFMI Maria Stoica yamaha Data 11 noiembrie 2011 09:51:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<iostream>
#include<fstream>
using namespace std;
#define Nmax 200000
long T[2][Nmax], start[Nmax], sel[Nmax];
void df(long nod)
{
     long p;
     p=start[nod];
     sel[nod]=1;
     while(p)
     {
         if(sel[T[0][p]]==0) df(T[0][p]);
         p=T[1][p];
     }
}

int main ()
{
	ifstream f("dfs.in");
	ofstream g("dfs.out");

	long n,m,k,i,j,nr=0;
	f>>n>>m;
    while(f>>i>>j)
     	{
         		k++;
         		T[0][k]=j;
         		T[1][k]=start[i];
         		start[i]=k;
        		k++;
         		T[0][k]=i;
         		T[1][k]=start[j];
         		start[j]=k;
     	}
    f.close();
    for(i=1;i<=n;i++)
    {
                if(sel[i]==0){df(i);nr++;}
    }
    g<<nr;
    g.close();
    return 0;

}