Cod sursa(job #2199244)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 26 aprilie 2018 23:08:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
#define dimn 100005

std::ifstream f("ctc.in");
std::ofstream g("ctc.out");

int N, M, nc;
std::list <int> adj[dimn];
std::vector <int> comp[dimn];
int ord[dimn], trj_time;
int lowlink[dimn];

std::stack <int> S;
bool is_stacked[dimn];
void tarjan(int start) {
    ord[start] = lowlink[start] = trj_time++;

    S.push(start); is_stacked[start] = 1;
    for (auto vec:adj[start])
        if (ord[vec] == -1)
            tarjan(vec),
            lowlink[start] = std::min(lowlink[start], lowlink[vec]);
        else if (is_stacked[vec])
            lowlink[start] = std::min(lowlink[start], lowlink[vec]);

    if(ord[start] == lowlink[start]) {
        int node;
        do {
            node = S.top(); S.pop();
            is_stacked[node] = 0;
            comp[nc].push_back(node);
        } while(node != start);
        nc++;
    }
}

void citire() {
    f >> N >> M;
    for (int i=0, x, y; i<M; i++)
        f >> x >> y,
        adj[x-1].push_back(y-1);
}
void rezolvare() {
    for (int i=0; i<N; i++)
        ord[i] = -1;
    for (int i=0; i<N; i++)
        if(ord[i] == -1)
            tarjan(i);

    g << nc << "\n";
    for (int i=0, j; i<nc; i++) {
        for (j=0; j<comp[i].size(); j++)
            g << comp[i][j]+1 << " " ;
        g << "\n" ;
    }
}

int main()
{
    citire();
    rezolvare();

    return 0;
}