Cod sursa(job #1283533)

Utilizator danalex97Dan H Alexandru danalex97 Data 5 decembrie 2014 20:06:43
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
using namespace std;

ifstream F("ctc.in");
ofstream G("ctc.out");

const int N = 100010;
const int M = 200010;

int n,m,mark[N],nbr;
vector<int> v[N],w[N],stack;
vector<int> ctc[N];

void go1(int x)
{
    mark[x] = 1;
    stack.push_back(x);
    for (int i=0;i<int(v[x].size());++i)
    {
        int y = v[x][i];
        if ( mark[y] == 0 )
            go1( y );
    }
}

void go2(int x)
{
    mark[x] = 1;
    ctc[nbr].push_back(x);
    for (int i=0;i<int(w[x].size());++i)
    {
        int y = w[x][i];
        if ( mark[y] == 0 )
            go2( y );
    }
}

void build_ctc()
{
    for (int i=1;i<=n;++i)
        if ( mark[i] == 0 )
            go1(i);
    memset(mark,0,sizeof(mark));
    for (int i=int(stack.size())-1;i>=0;--i)
    {
        int x = stack[i];
        if ( mark[x] == 0 )
        {
            ++nbr;
            go2(x);
        }
    }

    memset(mark,0,sizeof(mark));
}

int main()
{
    F>>n>>m;
    for (int i=1,x,y;i<=m;++i)
    {
        F>>x>>y;
        v[x].push_back(y);
        w[y].push_back(x);
    }

    build_ctc();
    G<<nbr<<'\n';
    for (int i=1;i<=nbr;++i,G<<'\n')
        for (int j=0;j<int(ctc[i].size());++j)
            G<<ctc[i][j]<<' ';
}