Cod sursa(job #2406213)

Utilizator eduardcadarCadar Eduard eduardcadar Data 15 aprilie 2019 15:08:16
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define dim 8192
#define nmax 100001
#define mmax 200001
int pz;
char ax[dim];
void cit(int &x) {
    x = 0;
    while (ax[pz] < '0' || ax[pz] > '9')
        if (++pz == dim) f.read(ax,dim), pz = 0;
    while (ax[pz] >= '0' && ax[pz] <= '9') {
        x = x * 10 + ax[pz] - '0';
        if (++pz == dim) f.read(ax,dim), pz = 0;
    }
}
int n, m, x, y, nr = 0, T[nmax];
bool u[nmax], ut[nmax], use[nmax];
vector<int> v[nmax], vt[nmax], a, sol[nmax];
void constr(int nod) {
    if (u[nod]) return;
    u[nod] = 1;
    for (int i = 0; i < v[nod].size(); ++i) constr(v[nod][i]);
    a.push_back(nod);
}
void dfs(int nod) {
    u[nod] = true, ++T[nod];
    for (int i = 0; i < v[nod].size(); ++i) if (!u[v[nod][i]]) dfs(v[nod][i]);
}
void dfst(int nod) {
    ut[nod] = true, ++T[nod];
    for (int i = 0; i < vt[nod].size(); ++i) if (!ut[vt[nod][i]]) dfst(vt[nod][i]);
}
int main()
{
    cit(n), cit(m);
    for (int i = 1; i <= m; ++i) {
        cit(x), cit(y);
        if (x-y) v[y].push_back(x), vt[x].push_back(y);
    }
    for (int i = 1; i <= n; ++i) constr(i);
    for (int i = 1; i <= n; ++i) u[i] = false;
    for (int k = 0; k < a.size(); ++k) {
        if (!u[a[k]]) dfs(a[k]);
        if (!ut[a[k]]) dfst(a[k]);
        for (int j = 1; j <= n; ++j) {
            if (T[j] == 2 && !use[j]) sol[nr].push_back(j), use[j] = true;
        }
        for (int i = 1; i <= n; ++i) T[i] = u[i] = ut[i] = 0;
        if (sol[nr].size()) ++nr;
    }

    g << nr << '\n';
    for (int i = 0; i < nr; ++i) {
        for (int j = 0; j < sol[i].size(); ++j) g << sol[i][j] << ' ';
        g << '\n';
    }
    return 0;
}