Cod sursa(job #1944536)

Utilizator radu.millio15Radu Millio radu.millio15 Data 29 martie 2017 10:10:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX=100000;
vector <int> G[NMAX+5];
int n;
vector <int>viz;
#define WHITE 0
#define GRAY 1
#define BLACK 2
void DFS(int u, int cc)
{
    viz[u]=cc;
    for(int j=0; j<(int)G[u].size(); j++)
    {
        int v=G[u][j];
        if(viz[v]==WHITE)
            DFS(v, cc);
    }
}
int main()
{
    int m,i,cc=0,u,v;
    FILE *fin, *fout;
    fin=fopen("dfs.in", "r");
    fout=fopen("dfs.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++)
    {
        fscanf(fin, "%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    viz.assign(n+1, WHITE);
    for(i=1; i<=n; i++)
    {
        if(viz[i]==WHITE)
        {
            cc++;
            DFS(i, cc);
        }
    }
    fprintf(fout, "%d\n", cc);
    return 0;
}