Cod sursa(job #2021836)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 14 septembrie 2017 20:01:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
#define Nmax 100005
#define Mmax 200005

using namespace std;

int* edge[Nmax];
int grad[Nmax],n,m,pos[Nmax];
int n1[Mmax],n2[Mmax],cnt;
bool viz[Nmax];

void dfs(int nod)
{
    viz[nod]=1;
    for(int i=1;i<=grad[nod];++i)
        if(!viz[edge[nod][i]]) dfs(edge[nod][i]);
}

int main()
{
    int i;
    ifstream cin("dfs.in");
    ofstream cout("dfs.out");
    cin>>n>>m;
    for(i=1;i<=m;++i)
    {
        cin>>n1[i]>>n2[i];
        ++grad[n1[i]]; ++grad[n2[i]];
    }
    for(i=1;i<=n;++i) edge[i] = new int[grad[i]+1];
    for(i=1;i<=m;++i)
    {
        edge[n1[i]][++pos[n1[i]]] = n2[i];
        edge[n2[i]][++pos[n2[i]]] = n1[i];
    }
    for(i=1;i<=n;++i)
        if(!viz[i])
        {
            ++cnt;
            dfs(i);
        }
    cout<<cnt<<"\n";
    return 0;
}