Cod sursa(job #1314215)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 11 ianuarie 2015 17:09:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <algorithm>
#include <stack>
using namespace std;

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

#define DIM 100001

struct node{
    int lowlink;
    int index;
};

int N, M, Index, CC, x, y;

bool B[DIM];
node D[DIM];

vector <int> G[DIM];
vector <vector <int> > Sol;
stack <int> S;

void Input();
void DFS(int);

int main()
{
    Input();
    for ( int i = 1; i <= N; ++i )
        if ( D[i].index == 0 )
            DFS(i);

    os << CC << '\n';
    for ( int i  = 0; i < CC; ++i )
    {
        for ( int j = 0; j < Sol[i].size(); ++j )
            os << Sol[i][j] << ' ';
        os << '\n';
    }

    is.close();
    os.close();
}

void Input()
{
    is >> N >> M;
    for ( int i = 1; i <= M; ++i )
    {
        is >> x >> y;
        G[x].push_back(y);
    }
}

void DFS(int x)
{
    Index++;
    B[x] = 1;
    S.push(x);
    D[x].index = Index;
    D[x].lowlink = Index;

    for ( const auto& v : G[x] )
    {
        if ( D[v].index == 0 )
        {
            DFS(v);
            D[x].lowlink = min(D[x].lowlink,D[v].lowlink);
        }
        else
            if ( B[v] )
                D[x].lowlink = min(D[x].lowlink,D[v].index);
    }

    if ( D[x].lowlink == D[x].index )
    {
        CC++;
        Sol.resize(CC);
        while ( !S.empty() && S.top() != x )
        {
            Sol[Sol.size()-1].push_back(S.top());
            B[S.top()] = 0;
            S.pop();
        }

        Sol[Sol.size()-1].push_back(S.top());
        B[S.top()] = 0;
        S.pop();
    }
}