Cod sursa(job #2111636)

Utilizator pistvanPeter Istvan pistvan Data 22 ianuarie 2018 15:26:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#define maxN 100001
using namespace std;

int N, M;
vector<int> Graph[maxN];
bool v[maxN];
int cnum;

void read()
{
    ifstream f("dfs.in");
    f>>N>>M;
    for (int i=1;i<=N;i++)
        Graph[i].push_back(0);
    for (int i=0, x, y;i<M;i++)
    {
        f>>x>>y;
        Graph[x].push_back(y);
        Graph[x][0]++;
        Graph[y].push_back(x);
        Graph[y][0]++;
    }
}

void dfs(int x)
{
    v[x]=1;
    for (int i=1;i<=Graph[x][0];i++)
        if (!v[Graph[x][i]])
            dfs(Graph[x][i]);
}

void write()
{
    ofstream g("dfs.out");
    g<<cnum;
}

int main()
{
    read();
    for (int i=1;i<=N;i++)
        if (!v[i])
            dfs(i), cnum++;
    write();
}