Cod sursa(job #1601212)

Utilizator gabime11Gabriel gabime11 Data 15 februarie 2016 20:15:08
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod
{
    int varf;
    int leg;
};
nod T[400009];
int START[100009];
int n,m,k,nr;
int VIZ[100009];
void citire()
{
    int a,b;
    k=0;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        k++;
        T[k].varf=b;
        T[k].leg=START[a];
        START[a]=k;
        k++;
        T[k].varf=a;
        T[k].leg=START[b];
        START[b]=k;
    }
}
void DFS(int vf)
{
    int i,x;
    VIZ[vf]=1;
    for(i=START[vf];i!=0;i=T[i].leg)
    {
        x=T[i].varf;
        if(VIZ[x]==0)
        {
            DFS(x);
        }
    }
}
void numarare()
{
    int i;
    nr=0;
    for(i=1;i<=n;i++)
    {
        if(VIZ[i]==0)
        {
            nr++;
            DFS(i);
        }
    }
}
int main()
{
    citire();
    numarare();
    fout<<nr;
    fin.close();
    fout.close();
    return 0;
}