Cod sursa(job #2197432)

Utilizator YouDontNeedMyNameJurcut Paul YouDontNeedMyName Data 22 aprilie 2018 10:11:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <bitset>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
bitset <100005> ap;
int n,m,vf,nr;
struct nod{
    int val;
    nod *next;
};
int varf[100005];
nod *lista[100005],*nonlista[100005],*sol[100005];
void add(int x, int y)
{
    nod *e=new nod;
    e->val=x;
    e->next=lista[y];
    lista[y]=e;
    nod *a=new nod;
    a->val=y;
    a->next=nonlista[x];
    nonlista[x]=a;
}
void ADD(int x, int y)
{
    nod *e=new nod;
    e->val=x;
    e->next=sol[y];
    sol[y]=e;
}
void ndfs(int x)
{
    ap[x]=1;
    nod *e=lista[x];
    while(e)
    {
        if(!ap[e->val])
        {
            ndfs(e->val);
        }
        e=e->next;
    }
    vf++;
    varf[vf]=x;
}
void dfs(int x)
{
    ap[x]=0;
    nod *e=nonlista[x];
    while(e)
    {
        if(ap[e->val])
        {
            dfs(e->val);
        }
        e=e->next;
    }
    ADD(x,nr);
}
int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin >> x >> y;
        add(x,y);
    }
    for(int i=1; i<=n; i++)
    {
        if(!ap[i])
            ndfs(i);
    }
    for(int i=vf; i>=1; i--)
    {
        if(ap[varf[i]])
        {
            nr++;
            dfs(varf[i]);
        }
    }
    cout << nr << '\n';
    for(int i=1; i<=nr; i++)
    {
        while(sol[i])
        {
            cout << sol[i]->val << ' ';
            sol[i]=sol[i]->next;
        }
        cout << '\n';
    }
    return 0;
}