Cod sursa(job #2336468)

Utilizator smatei16Matei Staicu smatei16 Data 5 februarie 2019 10:09:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define pb push_back
using namespace std;
vector<int>g[100005],gt[100005];
bool sel[100005],ok=false;
int v[100005],n,m,nr,nc;
void df(int x){
sel[x]=true;
for(int i=0;i<g[x].size();i++)
    if(!sel[g[x][i]])df(g[x][i]);
v[++nr]=x;
}
void dft(int x){
sel[x]=true;
if(ok)printf("%d ",x);
for(int i=0;i<gt[x].size();i++)
    if(!sel[gt[x][i]])dft(gt[x][i]);
}
int x,y,i;
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d %d",&x,&y);
        g[x].pb(y);gt[y].pb(x);
    }
    for(i=1;i<=n;i++)
        if(!sel[i])df(i);
    memset(sel,false,sizeof(sel));
    for(i=n;i>=1;i--)
        if(!sel[v[i]]){dft(v[i]);nc++;}
        printf("%d\n",nc);
        ok=true;
    memset(sel,false,sizeof(sel));
    for(i=n;i>=1;i--)
    if(!sel[v[i]]){
        dft(v[i]);
        printf("\n");
    }

    return 0;
}