Cod sursa(job #1847619)

Utilizator NicusorTelescu Nicolae Nicusor Data 14 ianuarie 2017 20:05:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <vector>

using namespace std;

vector <int> muchii[100001];
int cnt1=0;
bool pass[100001];
char s[50];

void dfs(int x)
{
    pass[x]=1;
    int l=muchii[x].size();
    for (int i=0;i<l;++i)
    {
        if (pass[muchii[x][i]]==0)
            dfs(muchii[x][i]);
    }
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int n,m;
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=m;++i)
    {
        int a=0,b=0;
        bool ab=0;
        gets(s);
        for (int j=0;s[j]!=0;++j)
        {
            if (s[j]==' ') ab++;
            else
            {
                if (ab==0) a=a*10+s[j]-'0';
                if (ab==1) b=b*10+s[j]-'0';
            }
        }
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    for (int i=1;i<=n;i++)
        if (pass[i]==0)
            cnt1++, dfs(i);
    printf("%d ",cnt1);
}