Cod sursa(job #1408712)

Utilizator danalex97Dan H Alexandru danalex97 Data 30 martie 2015 10:47:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda sim_oni_2010_ziua1 Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

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

int n,m,mk[N];
vector<int> v[N],w[N],st;
vector< vector<int> > ctc;

void dfs(int x)
{
    mk[x] = 1;
    for (int i=0;i<int(v[x].size());++i)
    {
        int y = v[x][i];
        if ( !mk[y] )
            dfs(y);
    }
    st.push_back( x );
}

vector<int> now;

void dfs2(int x)
{
    mk[x] = 1;
    for (int i=0;i<int(w[x].size());++i)
    {
        int y = w[x][i];
        if ( !mk[y] )
            dfs2(y);
    }
    now.push_back( x );
}

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);
    }
    for (int i=1;i<=n;++i)
        if ( mk[i] == 0 )
            dfs(i);
    memset(mk,0,sizeof(mk));
    while ( !st.empty() )
    {
        int x = st.back();
        st.pop_back();

        if ( mk[x] == 0 )
        {
            now.clear();
            dfs2(x);
            ctc.push_back(now);
        }
    }
    G<<ctc.size()<<'\n';
    for (int i=0;i<int(ctc.size());++i)
    {
        for (int j=0;j<int(ctc[i].size());++j)
            G<<ctc[i][j]<<' ';
        G<<'\n';
    }
}