Cod sursa(job #1216852)

Utilizator ValeraShulghin Valera Valera Data 5 august 2014 22:36:25
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>

using namespace std;

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

int n,m,a,b,graf[100001][3000],viz[100000],componente;

void DFS(int x)
{
    int i;
    viz[x]=1;
    for(i=1;i<=graf[x][0];i++)
    {
        if (viz[graf[x][i]]==0)
            DFS(graf[x][i]);
    }
}

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        graf[a][0]++;
        graf[b][0]++;
        graf[a][graf[a][0]]=b;
        graf[b][graf[b][0]]=a;
    }

    for(i=1;i<=n;i++)
        if (viz[i]==0)
        {
            componente++;
            DFS(i);
        }

    g<<componente;
    return 0;
}