Cod sursa(job #1170213)

Utilizator denisx304Visan Denis denisx304 Data 12 aprilie 2014 21:53:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <iostream>
#include <vector>
#define no_nodes 100005
using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

int vis[no_nodes], n, m, no_cc;

vector<int> graph[no_nodes];

void dfs(int node)
{
    vis[node] = 1;
    for (int i = 0; i < graph[node].size(); i ++)
        if (!vis[graph[node][i]])
            dfs(graph[node][i]);
}

int main()
{
    f >> n >> m;
    int t1, t2;
    for (int i = 0; i < m; i ++)
    {
        f >> t1 >> t2;
        graph[t1].push_back(t2);
        graph[t2].push_back(t1);
    }

    for (int i = 1; i <= n; i ++)
        if (!vis[i])
        {
            no_cc ++;
            dfs(i);
        }

    g << no_cc;

    f.close();
    g.close();
    return 0;
}