Cod sursa(job #688850)

Utilizator laurionLaurentiu Ion laurion Data 23 februarie 2012 21:52:18
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 3.28 kb
#define nume "ctc"

#include<cstdio>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<string>
#include<sstream>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<ctime>
#include<list>
#include<algorithm>

using namespace std;

#define _PARSARE_
#ifdef _PARSARE_
//////////////////////////////////////////////////////////////
//parsarea citirii
//////////////////////////////////////////////////////////////
#define DIM 8192
char ax[DIM+16];
int idx;

//numere NATURALE:
inline void cit_uint(int &x)
{
    x=0;
    while(ax[idx]<'0' || ax[idx]>'9')
        if(++idx==DIM)fread(ax, 1, DIM, stdin), idx=0;
    while(ax[idx]>='0' && ax[idx]<='9') {
        x=x*10+ax[idx]-'0';
        if(++idx==DIM)fread(ax,1, DIM, stdin),idx=0;
    }
}

//numere INTREGI:
inline void cit_int(int &x)
{
    x=0;
    while((ax[idx]<'0' || ax[idx]>'9') && (ax[idx]!='-'))
        if(++idx==DIM)fread(ax, 1, DIM, stdin), idx=0;

    int neg=0;
    if(ax[idx]=='-') {
        neg=1;
        if(++idx==DIM)fread(ax, 1, DIM, stdin),idx=0;
    }

    while(ax[idx]>='0' && ax[idx]<='9') {
        x=x*10+ax[idx]-'0';
        if(++idx==DIM)fread(ax,1, DIM, stdin),idx=0;
    }
    if(neg) x=-x;
}
#else
ifstream fin (nume".in");
#endif //_PARSARE_
ofstream fout(nume".out");
//#ifndef ONLINE_JUDGE
//	freopen("input.txt","r",stdin);
//#endif


#define foreach(V) for(vector<int>::iterator it=V.begin(),stop=V.end();it!=stop;++it)

int n;
int m;
vector<int> G[100000+10];
vector<int> sol[100000+10];

bool in_stack[100000+10];
stack<int> st;

bool viz[100000+10];

int min_lev[100000+10];

int nr=0;

void dfs_tarjan(int nod)
{
    st.push(nod);
    in_stack[nod]=true;
    viz[nod]=true;
    
    min_lev[nod]=idx;
    int initial_min_lev=idx;
    idx++;

    foreach(G[nod]) {
        if(!viz[*it]) {
            dfs_tarjan(*it);
            min_lev[nod]=min(min_lev[*it],min_lev[nod]);
        } else if(in_stack[*it])
            min_lev[nod]=min(min_lev[*it],min_lev[nod]);
    }
    if(min_lev[nod]==initial_min_lev) {
        int x;
        do {
            x=st.top();
            st.pop();
            sol[nr].push_back(x);
            in_stack[x]=false;
        } while(x!=nod);
        nr++;
    }
}
bool cmp(vector<int> a, vector<int> b)
{
    return a[0]<b[0];
}
int main()
{
#ifdef _PARSARE_
    freopen(nume".in","r",stdin);
    cit_uint(n);
    cit_uint(m);
#else
    fin>>n>>m;
#endif

    for(; m; --m) {
        int x,y;
#ifdef _PARSARE_
        cit_uint(x);
        cit_uint(y);
#else
        fin>>x>>y;
#endif
        G[x].push_back(y);
    }
    
    idx=0;

    for(int i=1; i<=n; ++i)
        if(!viz[i])
            dfs_tarjan(i);

    fout<<nr<<'\n';
//    for(int i=0;i<nr;++i,cerr<<'\n')
//    {
////        cerr<<sol[nr].size()<<' ';
//        foreach(sol[i])
//            cerr<<*it<<' ';
//    }
    for(int i=0;i<nr;++i) {
        sort(sol[i].begin(),sol[i].end()); //sortare degeaba
    }
    sort(sol,sol+nr,cmp);//sortare degeaba
    for(int i=0;i<nr;++i,fout<<'\n')
    {
//        fout<<sol[i].size()<<' ';
        foreach(sol[i])
            fout<<*it<<' ';
    }

    fout.close();
    return 0;
}