Cod sursa(job #1667861)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 29 martie 2016 12:09:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
// Template v2
#define pb push_back
#define mp make_pair
#define first x
#define second y
#define l(x) x<<1
#define r(x) x<<1 | 1
#define lsb(x) x & -x
#define MOD1 3000017
#define MOD2 3000541
#include<bits/stdc++.h>
#include <bitset>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PKK;
// primes less than 100
const int PRIM[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
const int CMAX = 10005;
const int MOD = 666013;
const int NMAX = 200069;
const short INF16 = 32000;
const int INF = 1e9 + 10;
const LL INF64 = LL(1e18);
const LD EPS = 1e-9, PI = acos(-1.0);

struct vertex{
    int l, id, c;
    bool stack;
};
vertex V[NMAX];
VI G[NMAX];
VI rs[NMAX];
int x,y,ind,n,m;
int S[NMAX], s;
int c=0;
void dfs(int v)
{
    V[v].id=ind;
    V[v].l=ind;
    ind++;
    S[++s]=v;
    V[v].stack=true;
    for(int i=0; i<G[v].size(); ++i)
    {
        int w=G[v][i];
        if(V[w].id==0)
        {
            dfs(w);
            V[v].l=min(V[v].l, V[w].l);
        }else
        if(V[w].stack)
            V[v].l=min(V[v].l, V[w].l);
    }
    if(V[v].id == V[v].l)
    {
        c++;
        int x;
        do{
            x=S[s--];
            V[x].stack=0;
            rs[c].pb(x);
            
        }while(x!=v);
    }
}

void read()
{
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        cin>>x>>y;
        G[x].pb(y);
    }
    ind=1;
    for(int i=1; i<=n; ++i)
        if(V[i].id==0)
            dfs(i);
    cout<<c<<"\n";
    
    for(int i=1; i<=n; ++i, cout<<"\n")
        for(int j=0; j<rs[i].size(); ++j)
            cout<<rs[i][j]<<" ";
}

int main() {
    assert(freopen("ctc.in", "rt", stdin));
    assert(freopen("ctc.out", "wt", stdout));
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << setprecision(16) << fixed;
    
    read();
    
    return 0;
}