Cod sursa(job #950198)

Utilizator dudutCancel Radu Constantin dudut Data 16 mai 2013 08:36:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <cstdio>
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>
 
using namespace std;
FILE *f = fopen("ctc.in", "r");
FILE *g = fopen("ctc.out","w");


#define Min(a, b)  ((a) < (b) ? (a) : (b))
 
vector <int> adj[100005], con, idx, lowlink, in_stack;
 
vector < vector <int> > mat;
 
stack <int> S;
 
int indecs;
 
void read_in(vector <int>* adj, int& n) 
{
    int cnt_edges, x, y;
 
	fscanf(f, "%d", &n);
    for ( fscanf(f, "%d", &cnt_edges); cnt_edges > 0; -- cnt_edges) {
		fscanf(f, "%d%d", &x, &y);
        adj[x - 1].push_back(y - 1);
	}

}
 
void print_out()
{ 
	fprintf (g, "%d\n", mat.size());
    for (size_t i = 0; i < mat.size(); ++ i) {
        for (size_t j = 0; j < mat[i].size(); ++ j)
            fprintf(g, "%d ", mat[i][j] + 1);
        fprintf(g, "\n");
    }
}
 
void tarjan(const int n, const vector <int>* adj)
{
    idx[n] = lowlink[n] = indecs;
    indecs ++;
    S.push(n), in_stack[n] = 1;
 
    vector <int>::const_iterator it;
    for (it = adj[n].begin(); it != adj[n].end(); ++ it) {
        if (idx[*it] == -1)
            tarjan(*it, adj),
            lowlink[n] = Min(lowlink[n], lowlink[*it]);
        else if (in_stack[*it])
            lowlink[n] = Min(lowlink[n], lowlink[*it]);
    }
	
    if (idx[n] == lowlink[n]) {
        con.clear();
        int node;
        do {
            con.push_back(node = S.top());
            S.pop(), in_stack[node] = 0;
        }
        while (node != n);
        mat.push_back(con);
    }
}
 
int main(void)
{
    int n;
    read_in(adj, n);
 
    idx.resize(n), lowlink.resize(n), in_stack.resize(n);
    idx.assign(n, -1), in_stack.assign(n, 0);
    for (int i = 0; i < n; ++ i) if (idx[i] == -1)
        tarjan(i, adj);
 
    print_out();
 
    return 0;
}