Cod sursa(job #1597878)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 12 februarie 2016 13:56:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define MAXN 100005

vector <int> edge[MAXN], edgeT[MAXN], order, solution[MAXN];
int N, M;

int used[MAXN], height[MAXN];

void DF_Plus (int node)
{
    used[node] = 1;
    for (int i = 0; i < edge[node].size(); ++i)
        if (!used[edge[node][i]])
            DF_Plus(edge[node][i]);
    order.push_back(node);
}

void DF_Minus (int node, int component)
{
    height[node] = component;
    for (int i = 0; i < edgeT[node].size(); ++i)
        if (!height[edgeT[node][i]])
            DF_Minus(edgeT[node][i], component);
}

int main()
{
    fin >>N >>M;

    for (int i = 1; i <= M; ++i)
    {
        int x, y;
        fin >>x >>y;
        edge[x].push_back(y);
        edgeT[y].push_back(x);
    }

    for (int i = 1; i <= N; ++i)
        if (!used[i])
            DF_Plus(i);

    int component = 1;

    for (; order.size(); order.pop_back())
        if (!height[order.back()])
        {
            DF_Minus(order.back(), component);
            ++component;
        }

    for (int i = 1; i <= N; ++i)
        solution[height[i]].push_back(i);

    fout <<--component <<'\n';

    for (int i = 1; i <= component; ++i){
        for (int j = 0; j < solution[i].size(); ++j)
            fout <<solution[i][j] <<' ';
        fout <<'\n';
    }


    return 0;
}