Cod sursa(job #1328876)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 28 ianuarie 2015 20:47:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

#define Nmax 100100
#define neighbour(G) G[node][i]

using namespace std;

vector <int> Graph[Nmax], GraphT[Nmax], Component[Nmax];
int N, Components, Index, Order[Nmax];
bool seen[Nmax];

void Dfs(int node) {

    seen[node] = true;
    Component[Components].push_back(node);

    for(int i = 0; i < GraphT[node].size(); i++)
        if(!seen[neighbour(GraphT)])
            Dfs(neighbour(GraphT));
}
void sortTop(int node) {

    seen[node] = true;

    for(int i = 0; i < Graph[node].size(); i++)
        if(!seen[neighbour(Graph)])
            sortTop(neighbour(Graph));

    Order[++Index] = node;
}
void Solve() {

    int i;

    for(i = 1; i <= N; i++)
        if(!seen[i])
            Dfs(i);

    reverse(Order + 1, Order + N + 1);
    memset(seen, 0, sizeof(seen));

    for(i = 1; i <= N; i++)
        if(!seen[Order[i]]) {
            Components++;
            Dfs(Order[i]);
        }
}
void Read() {

    int x, y, M;
    ifstream in("ctc.in");

    in >> N >> M;
    while(M--) {
        in >> x >> y;
        Graph[x].push_back(y);
        GraphT[y].push_back(x);
    }

    in.close();
}
void Write() {

    int i, j;
    ofstream out("ctc.out");
    out << Components << '\n';

    for(i = 1; i <= Components; i++) {
        for(j = 0; j < Component[i].size(); j++)
            out << Component[i][j] << ' ';
        out << '\n';
    }

    out << '\n';
    out.close();
}
int main() {

    Read();
    Solve();
    Write();

    return 0;
}