Cod sursa(job #2195451)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 16 aprilie 2018 13:39:16
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;
ifstream in ("dfs.in");
ofstream out ("dfs.out");
int start[100005],t[2][400005],r[100005],n,m;
void citire ()
{
    in>>n>>m;
    int i,k=0,a,b;
    for(i=1;i<=m;i++)
    {
        in>>a>>b;
        k++;
        t[0][k]=b;
        t[1][k]=start[a];
        start[a]=k;
        k++;
        t[0][k]=a;
        t[1][k]=start[b];
        start[b]=k;
    }
}
void recur (int poz)
{
        r[poz]=0;
        for(int i=start[poz];i!=0;i=t[1][i])
        {
            if(r[t[0][i]]==-1)
                recur(t[0][i]);
        }
}
int main()
{
    int i,cnt=0;
    citire();
    for(i=1;i<=n;i++)
        r[i]=-1;
    for(i=1;i<=n;i++)
    {
        if(r[i]==-1)
        {
            recur(i);
            cnt++;
        }
    }
    out<<cnt;
    return 0;
}