Cod sursa(job #2077934)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 28 noiembrie 2017 19:02:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#include <vector>
using namespace std;
vector <int> v[100001];
vector <int>::iterator it;
int n,m,i,j,a[100001];
void dfs(int i)
{

    if(!a[i])
    {
        a[i]=1;
        for(int j=0;j<v[i].size();j++)
            if (a[v[i][j]]==0)dfs(v[i][j]);
    }
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    while(m)
    {
        scanf("%d %d\n",&i,&j);
        v[i].push_back(j);
        v[j].push_back(i);
        m--;
    }
    for(i=1;i<=n;i++)
        if(!a[i])
        {
            dfs(i);
            m++;
        }
    printf("%d\n",m);
    return 0;
}