Cod sursa(job #1801683)

Utilizator HuskyezTarnu Cristian Huskyez Data 9 noiembrie 2016 15:07:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>

#define infile "ctc.in"
#define outfile "ctc.out"

using namespace std;

ifstream in(infile);
ofstream out(outfile);

int n, m;
int x, y;

vector<int> graph[100005];
vector<int> graphT[100005];
vector<int> component[100005];

bool vis[100005];
vector<int> discovered;
int roots[100005];
vector<int> nodes;

int count;

void firstDFS(int node)
{
    vis[node] = true;
    for(vector<int> :: iterator it=graph[node].begin(); it!=graph[node].end(); it++){
        if(!vis[*it]){
            firstDFS(*it);
        }
    }
    discovered.push_back(node);
}

void secondDFS(int node, int root)
{
    roots[node] = root;
    nodes.push_back(node);
    for(vector<int> :: iterator it=graphT[node].begin(); it!=graphT[node].end(); it++){
        if(!roots[*it]){
            secondDFS(*it, root);
        }
    }
}

int main()
{
    in >> n >> m;

    for(int i=0; i<m; i++){
        in >> x >> y;
        graph[x].push_back(y);
        graphT[y].push_back(x);
    }

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

    for(; discovered.size(); discovered.pop_back()){
        if(!roots[discovered.back()]){
            count++;
            secondDFS(discovered.back(), count);
        }
    }

    for(int i=1; i<=n; i++){
        component[roots[i]].push_back(i);
    }

    out << count << '\n';
    for(int i=1; i<=count; i++){
        for(vector<int> :: iterator it=component[i].begin(); it!=component[i].end(); it++){
            out << *it << ' ';
        }
        out << '\n';
    }

    return 0;
}