Cod sursa(job #1089641)

Utilizator mihai995mihai995 mihai995 Data 21 ianuarie 2014 20:24:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 1 + 1e5;

vector<int> graph[N], trans[N];
int stack[N];
bool use[N];

ifstream in("ctc.in");
ofstream out("ctc.out");

void dfs(vector<int>* graph, int x, void (*work)(int)){
    use[x] = true;

    for (vector<int> :: iterator it = graph[x].begin() ; it != graph[x].end() ; it++)
        if (!use[*it])
            dfs(graph, *it, work);

    work(x);
}

void addToStack(int x){
    stack[ ++stack[0] ] = x;
}

void print(int x){
    out << x << ' ';
}

void doNothing(int x){}

int main(){
    int n, m, x, y;
    in >> n >> m;

    while (m--){
        in >> x >> y;
        graph[x].push_back(y);
        trans[y].push_back(x);
    }

    memset(use, false, sizeof(use));
    for (int i = 1 ; i <= n ; i++)
        if (!use[i])
            dfs(trans, i, addToStack);

    memset(use, false, sizeof(use));
    int ans = 0;
    while (stack[0]){
        x = stack[ stack[0]-- ];
        if (!use[x]){
            dfs(graph, x, doNothing);
            ans++;
        }
    }
    out << ans << "\n";

    stack[0] = n;
    memset(use, false, sizeof(use));
    while (stack[0]){
        x = stack[ stack[0]-- ];
        if (!use[x]){
            dfs(graph, x, print);
            out << '\n';
        }
    }

    return 0;
}