Cod sursa(job #2085020)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 9 decembrie 2017 15:55:20
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define MN 100005
#define MM 200005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int N, M, ns, k, post[MN];
bitset <MN> viz;
typedef struct nod
{
    int vf;
    nod* next;
} *pnod;
pnod G[MN], Gt[MN], Sol[MN];

void add(pnod graf[], int a, int b)
{
    pnod p = new nod;
    p->vf = b;
    p->next = graf[a];
    graf[a] = p;
}
void add(pnod &graf, int x)
{
    pnod p = new nod;
    p->vf = x;
    p->next = graf;
    graf = p;
}

void dfs(int nod)
{
    viz.set(nod);
    for(pnod p = G[nod]; p; p = p->next)
        if(!viz.test(p->vf))
            dfs(p->vf);
    post[++k] = nod;
}

void dfsT(int nod)
{
    viz.set(nod, 0);
    add(Sol[ns], nod);
    for(pnod p = Gt[nod]; p; p = p->next)
        if(viz.test(p->vf))
            dfsT(p->vf);
}

int main()
{
    in >> N >> M;
    for(int a, b, i = 1; i <= M; ++i)
    {
        in >> a >> b;
        add(G, a, b);
        add(Gt, b, a);
    }
    for(int i = 1; i <= N; ++i)
        if(!viz.test(i))
            dfs(i);
    for(int i = k; i; --i)
        if(viz.test(post[i]))
        {
            ns++;
            dfsT(post[i]);
        }
    out << ns << '\n';
    for(int i = 1; i <= ns; ++i)
    {
        for(pnod p = Sol[i]; p; p = p->next)
            out << p->vf << ' ';
        out << '\n';
    }
    in.close(), out.close();
    return 0;
}