Cod sursa(job #780778)

Utilizator vitaleamaldur vitalik vitalea Data 21 august 2012 18:27:33
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>


#define ALB 1
#define GRI 2
#define NEGRU 3

using namespace std;

int n, m;
vector< vector<int> > graph, graphT, solution;
vector<int> c;
stack<int> s;

void dfs(int node)
{
    c[node] = GRI;
    for(int i = 0; i < graph[node].size(); i++)
    {
        if(c[graph[node][i]] == ALB)
        {
            dfs(graph[node][i]);
        }
    }
    s.push(node);
    c[node] = NEGRU;
}

void dfsT(int node, int index)
{
    solution.resize(index + 1);
    solution[index].push_back(node);
    c[node] = GRI;
    for(int i = 0; i < graphT[node].size(); i++)
    {
        if(c[graphT[node][i]] == ALB)
        {
            dfsT(graphT[node][i], index);
        }
    }
    c[node] = NEGRU;
}

void kosaraju()
{
    c = vector<int> (n + 1, ALB);
    for(int i = 1; i < n + 1; i++)
    {
        if(c[i] == ALB)
        {
            dfs(i);
        }
    }
    c = vector<int> (n + 1, ALB);

    int i = 0;
    while(!s.empty())
    {
        int node = s.top();
        s.pop();
        if(c[node] == ALB)
        {
            dfsT(node, i);
            i++;
        }
    }
}

int main()
{
    ifstream in ("ctc.in");
    ofstream out ("ctc.out");
    int x, y;
    in >> n >> m;
    graph.resize(n + 1);
    graphT.resize(n + 1);
    for(int i = 0; i < m; i++)
    {
        in >> x >> y;
        graph[x].push_back(y);
        graphT[y].push_back(x);
    }
    kosaraju();
    out << solution.size() << '\n';
    for(int i = 0; i < solution.size(); i++)
    {
        for(int j = 0; j < solution[i].size(); j++)
        {
            out << solution[i][j] << " ";
        }
        out << '\n';
    }
    out.close();
    in.close();
    return 0;
}