Cod sursa(job #2380980)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 15 martie 2019 19:24:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>
#define LIM 1<<17
/// TONI BO$$ was here
/// #MLC

using namespace std;
char BUF[LIM];
int poz;

inline char getChar(){
    poz++;
    if(poz>=LIM){
    	fread(BUF,LIM,1,stdin);
    	poz=0;
    }
    return BUF[poz];
}

inline int getNr(){
    int r=0, semn=1;
    char ch=getChar();
    while(isdigit(ch)==0 && ch!='-') ch=getChar();
    if(ch=='-'){
        semn=-1;
        ch=getChar();
    }
    while(isdigit(ch)!=0){
        r=r*10+semn*(ch-'0');
        ch=getChar();
    }
    return r;
}

vector <int> G[100001];
vector <int> Gt[100001];
int f[100001],ctc;
vector <int> steve;
vector <int> rez[100001];

void dfs1(int i)
{
    f[i]=1;
    for(auto it : G[i])
        if(!f[it])
            dfs1(it);
    steve.push_back(i);
}

void dfs2(int i)
{
    f[i]=ctc;
    for(auto it : Gt[i])
        if(!f[it])
            dfs2(it);
    rez[ctc].push_back(i);
}

int main()
{
    int n,m,i,x,y;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    poz=LIM;
    n=getNr();
    m=getNr();
    for(i=1; i<=m; i++)
    {
        x=getNr();
        y=getNr();
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(i=1; i<=n; i++)
        if(!f[i])
            dfs1(i);
    for(i=1; i<=n; i++)
        f[i]=0;
    while(!steve.empty())
    {
        int z=steve.back();
        steve.pop_back();
        if(f[z])
            continue ;
        ++ctc;
        f[z]=ctc;
        dfs2(z);
    }
    printf("%d\n",ctc);
    for(i=1; i<=ctc; i++)
    {
        for(auto it : rez[i])
            printf("%d ",it);
        printf("\n");
    }

    return 0;
}