Cod sursa(job #1216844)

Utilizator ValeraShulghin Valera Valera Data 5 august 2014 22:20:09
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>

using namespace std;

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

int n,m,a,b,graf[100][100],viz[100],componente,maxim;


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

int main()
{
    int i,j;
    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;
    }

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

    g<<maxim;
    return 0;
}