Cod sursa(job #2212211)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 13 iunie 2018 16:59:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
struct nod
{
    int vecin, leg;
};
nod L[400003];
int n,m,i,x,y,start[100005],k,nrc,viz[100005];
void DFS(nod L[],int vfstart, int viz[],int k)
{
    int i;
    viz[vfstart]=k;
    for(i=start[vfstart];i!=0;i=L[i].leg)
    {
        if(viz[L[i].vecin]==0)
        {
            DFS(L,L[i].vecin, viz, k);
        }
    }
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        start[i]=0;
    }
    k=0;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        k++;
        L[k]={y,start[x]};
        start[x]=k;
        k++;
        L[k]={x,start[y]};
        start[y]=k;
    }
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
    }
    nrc=0;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            nrc++;
            DFS(L,i,viz,nrc);
        }
    }
    fout<<nrc;
    fin.close();
    fout.close();
    return 0;
}