Cod sursa(job #1948174)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 31 martie 2017 19:58:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>

using namespace std;

int START[100002],T[2][400002],viz[100002];

ifstream fin("dfs.in");
ofstream fout("dfs.out");

void DFS(int vf)
{
    int i,x;
    viz[vf]=1;
    for(i=START[vf];i!=-1;i=T[1][i])
    {
        x=T[0][i];
        if(viz[x]==0)
            DFS(x);
    }
}


int main()
{
    int i, x, y, n, m, k, c=0;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        START[i]=-1;
    }
    k=0;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        k++;
        T[0][k]=y;
        T[1][k]=START[x];
        START[x]=k;
        k++;
        T[0][k]=x;
        T[1][k]=START[y];
        START[y]=k;
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            c++;
            DFS(i);
        }
    }
    fout<<c;

    fin.close();
    fout.close();

    return 0;
}