Cod sursa(job #2507678)

Utilizator Rares31100Popa Rares Rares31100 Data 10 decembrie 2019 18:03:29
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>

using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

int n,m;
int mc[400001];
int urm[400001];
int lst[200001];
bool viz[200001];

void dfs(int x)
{
    viz[x]=1;

    for(int i=lst[x];i!=0;i=urm[i])
        if(!viz[ mc[i] ])
            dfs(mc[i]);
}

int main()
{
    cin>>n>>m;
    for(int i,j,k=1;k<=2*m;k+=2)
    {
        cin>>i>>j;

        mc[k]=i,mc[k+1]=j;
        urm[i]=lst[j],urm[j]=lst[i];
        lst[i]=k+1,lst[j]=k;
    }

    int nr=0;
    for(int i=1;i<=n;i++)
        if(!viz[i])
        {
            nr++;
            dfs(i);
        }

    cout<<nr;
}