Cod sursa(job #2326563)

Utilizator CojocaruVicentiuCojocaru Vicentiu CojocaruVicentiu Data 23 ianuarie 2019 17:39:43
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include<fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

struct nod{
    int x;
    nod *urm;
};
nod *Li[100010], *q,*ind[100010];
int n,m,i,a,b,nr,viz[100010];

void dfs(int j)
{
    viz[j]=1;
    while(ind[j]!=NULL)
    {
        if(viz[ind[j]->x]==0)
        {
            dfs(ind[j]->x);
        }
        ind[j]=ind[j]->urm;
    }

}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        q=new nod;
        q->urm=Li[a];
        q->x=b;
        Li[a]=q;
        q=new nod;
        q->urm=Li[b];
        q->x=a;
        Li[b]=q;
    }

    for(i=1;i<=n;i++)
        ind[i]=Li[i];
    for(i=1;i<=n;i++)
        if(viz[i]==0)
        {
            dfs(i);
            nr++;
        }
    fout<<nr;


    fin.close();
    fout.close();
    return 0;
}