Cod sursa(job #780850)

Utilizator vitaleamaldur vitalik vitalea Data 22 august 2012 12:18:25
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>


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

using namespace std;

int n, m, index;
vector< vector<int> > graph, solution;
vector<int> c, idx, lowlink;
stack<int> s;

void tarjan(int node)
{
    idx[node] = lowlink[node] = index;
    index++;
    s.push(node);
    c[node] = NEGRU;

    for(int i = 0; i < graph[node].size(); i++)
    {
        if(idx[graph[node][i]] == 0)
        {
            tarjan(graph[node][i]);
            lowlink[node] = min(lowlink[node], lowlink[graph[node][i]]);
        }
        else
        {
            if(c[graph[node][i]] == NEGRU)
            {
                lowlink[node] = min(lowlink[node], idx[graph[node][i]]);
            }
        }
    }

    if(lowlink[node] == idx[node])
    {
        solution.resize(solution.size() + 1);
        int tmp;
        do
        {
            tmp = s.top();
            s.pop();
            solution[solution.size() - 1].push_back(tmp);
        } while(tmp != node);
    }
}

void ctc_tarjan()
{
    index = 0;
    c = vector<int> (n + 1, ALB);
    idx = vector<int> (n + 1, 0);
    lowlink = vector<int> (n + 1, 0);

    for(int i = 1; i < n + 1; i++)
    {
        if(idx[i] == 0)
        {
            tarjan(i);
        }
    }
}

int main()
{
    ifstream in ("ctc.in");
    ofstream out ("ctc.out");
    int x, y;
    in >> n >> m;
    graph.resize(n + 1);
    for(int i = 0; i < m; i++)
    {
        in >> x >> y;
        graph[x].push_back(y);
    }
    ctc_tarjan();

    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;
}