Cod sursa(job #866577)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 28 ianuarie 2013 13:01:28
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct node
{
    int nr;
    node *next;
} *v[100001]; bool exp[100001];
int m,n,nr,ma;

void build_graph ()
{
    int a,b;
    node *d;
    fin>>a>>b;
    d=new node;
    d->nr=a;
    d->next=v[b];
    v[b]=d;
    d=new node;
    d->nr=b;
    d->next=v[a];
    v[a]=d;
}

void DFS (int i)
{
    nr++;
    exp[i]=1;
    node *d=v[i];
    while (d!=NULL)
    {
        if (!exp[d->nr]) DFS (d->nr);
        d=d->next;
    }
}

int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        build_graph ();
    }
    for (i=1;i<=n;i++)
    {
        nr=0;
        if (!exp[i]) DFS(i);
        if (nr>ma) ma=nr;
    }
    fout<<ma;
}