Cod sursa(job #1792067)

Utilizator Emil64Emil Centiu Emil64 Data 29 octombrie 2016 23:29:53
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <vector>

int n, m;
std::vector<int> v[100001];
int lg, c=0;
bool viz[100001]={0};

void dfs( int x )
{
    int i, _lg;
    viz[x] = 1;
    _lg=v[x].size();
    for (i=0; i<_lg; i++)
        if (viz[v[x][i]]==0)
            dfs(v[x][i]);
}
char buff[20000];int pos=0;
FILE*f=freopen("dfs.in","r",stdin);
FILE*g=freopen("dfs.out","w",stdout);
inline void read(int &nr){
    while(buff[pos] < '0' || buff[pos] > '9')if(++pos == 20000) fread(buff, 1, 20000, stdin), pos = 0;
    nr = 0;
    while('0' <= buff[pos] && buff[pos] <= '9') {nr = nr * 10 + buff[pos] - '0';if(++pos == 20000) fread(buff, 1, 20000, stdin), pos = 0;}
}
int main()
{
    fread(buff, 1, 20000, stdin), pos = 0
    int i, x, y;
    read(n);
    read(m);
    for (i=0; i<m; i++)
    {
        read(x);read(y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (i=1;i<=n;i++)
        if (viz[i]==0)
            c++, dfs(i);


    printf("%d\n", c);
}