Cod sursa(job #1366152)

Utilizator viuscenkoViktor Iuscenko viuscenko Data 28 februarie 2015 20:12:53
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.5 kb
#include <bits/stdc++.h>

using namespace std;

#define     mp              make_pair
#define     fs              first
#define     sc              second
#define     pob             pop_back
#define     pub             push_back
#define     eps             1E-7
#define     sz(a)           a.size()
#define     count_one       __builtin_popcount;
#define     count_onell     __builtin_popcountll;
#define     fastIO          ios_base::sync_with_stdio(false)
#define     PI              (acos(-1.0))
#define     linf            (1LL<<62)//>4e18
#define     inf             (0x7f7f7f7f)//>2e9

#define DEBUG 1
#ifdef DEBUG
#define D(x) x
#else
#define D(x)
#endif

#define MAXN 100001

FILE *in = fopen("ctc.in", "r");
FILE *out = fopen("ctc.out", "w");

struct graph {
    int index;
    int lowindex;
    bool isRemoved;

    graph() { this->index = -1; this->lowindex = -1; this->isRemoved = true; }

    graph(int a, int b, bool c) {
        this->index = a;
        this->lowindex = b;
        this->isRemoved = c;
    }
} *g[MAXN];

int n, m, indecs, tconexe = 0;
stack<int> St;
vector<int> vec[MAXN];
vector<vector<int>> elem;

void tareConex(int nod) {
    //index = 1;
    g[nod]->index = indecs;
    g[nod]->lowindex = indecs;
    indecs++;
    g[nod]->isRemoved = false;
    St.push(nod);

    for(auto it = vec[nod].begin(); it != vec[nod].end(); it++) {
        if(g[*it]->index == -1) {
            tareConex(*it);
            g[nod]->lowindex = min(g[nod]->lowindex, g[*it]->lowindex);
        } else {
            if(!g[*it]->isRemoved)
                g[nod]->lowindex = min(g[nod]->lowindex, g[*it]->index);
        }
    }

    int x;
    vector<int> local;
    if(g[nod]->index == g[nod]->lowindex) {
        do {
            x = St.top(); St.pop();
            g[x]->isRemoved = true;
            local.pub(x);
        } while(x != nod);
        elem.pub(local);
        tconexe++;
    }
}

int main()
{
    int x, y;
    fscanf(in, "%d%d", &n, &m);

    for(int i = 1; i <= m; ++i) {
        fscanf(in, "%d%d", &x, &y);
        g[i] = new graph();
        g[i]->index = -1;
        vec[x].pub(y);
    }

    for(int i = 1; i <= n; ++i) {
        if(g[i]->index == -1)
            tareConex(i);
    }

    fprintf(out, "%d\n", tconexe);
    for(int i = 0; i < tconexe; ++i) {
        for(auto it = elem[i].begin(); it != elem[i].end(); it++)
            fprintf(out, "%d ", *it);
        fprintf(out, "\n");
    }
    return 0;
}