Cod sursa(job #890259)

Utilizator alexteStefanescu Alexandru Catalin alexte Data 24 februarie 2013 22:45:08
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
using namespace std;
int n,m,start[100001],t[2][200002],viz[100001],c,i;
void citire()
{
    int a,b,i,k=0;
    ifstream fin("dfs.in");
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>a>>b;
        k++;
        t[0][k]=a;
        t[1][k]=start[a];
        start[a]=k;
        k++;
        t[0][k]=b;
        t[1][k]=start[b];
        start[b]=k;
    }

}
void df(int vf)
{
    int stiva[100001],i,j,k=0;
    k++;
    stiva[k]=vf;
    viz[vf]=1;
    k=1;
   while(k>0)
    {
        i=start[stiva[k]];
        while(i!=0 && viz[t[0][i]]==1)
        i=t[1][i];
        if(i!=0)
        {
            k++;
            stiva[k]=t[0][i];
            viz[t[0][i]]=1;
        }
        else k--;
    }
}
int main()
{
    ofstream fout("dfs.out");
    citire();
    for(i=1;i<=n;++i)
        if(viz[i]==0)
        {
            c++;
            df(i);
        }
    fout<<c/2;
    fout.close();
    return 0;
}