Cod sursa(job #891850)

Utilizator myshuSpatariu Mihai-Constantin myshu Data 25 februarie 2013 20:40:10
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
using namespace std;
int tata[100001];
void updatetata(int a, int b)
{
    if(tata[b]!=-1)updatetata(a,tata[b]);
     if(b!=a)tata[b]=a;
}
int main()
{
    ifstream fcin("dfs.in");
    ofstream fcout("dfs.out");
    int m,i,a,b,n,k=0;
    fcin>>n>>m;
    for(i=1;i<=m;i++)
    {fcin>>a>>b;
     if(tata[a]==0&&tata[b]==0){tata[a]=-1;tata[b]=a;}
     else if(tata[a]==0&&tata[b]==-1){tata[a]=b;}
     else if(tata[b]==0&&tata[a]==-1){tata[b]=a;}
     else if(tata[a]==-1&&tata[b]==-1){tata[b]=a;}
     else {while(tata[a]!=-1)a=tata[a];
            updatetata(a,b);}
     }
     for(i=1;i<=n;i++)
     if(tata[i]==-1||tata[i]==0)k++;
     fcout<<k<<'\n';
    return 0;
}