Cod sursa(job #964601)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 21 iunie 2013 17:47:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
/*
    3.0 featuring TARJAN
*/
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <ctime>
#include <utility>
#include <stack>
#include <set>

using namespace std;

const int NMAX = 100005;

ofstream cout("ctc.out");

vector <int> G[NMAX], idx(NMAX, -1), lowlink(NMAX), con;
vector< vector<int> > C;
bitset <NMAX> in_Stack;
stack <int> Stack;
int n , m, indecs;

void read();
void tarjan(int);
void write();

inline int min(int a, int b)
{
    if( a > b)
        return b;
    return a;
}

int main()
{
    read();

    for(int i = 1 ; i <= n ; ++ i)
        if(idx[i] == -1)
            tarjan(i);
    write();
    return 0;
}

void read()
{
    ifstream cin("ctc.in");
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++ i)
    {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
    }
}

void tarjan(int node)
{
    idx[node] = lowlink[node] = ++indecs;
    Stack.push(node);
    in_Stack[node] = true;
    for(vector<int> :: iterator it = G[node].begin();  it != G[node].end() ; ++ it)
        if(idx[*it] == -1)
        {
            tarjan(*it);
            lowlink[node] = min(lowlink[node] , lowlink[*it]);
        }
        else if(in_Stack[*it])
                lowlink[node] = min(lowlink[node] , lowlink[*it]);
    if(idx[node] == lowlink[node])
    {
        con.clear();
        int nod;
        do
        {
            con.push_back(nod = Stack.top()); //initialize
            Stack.pop(); in_Stack[nod] = false;
        } while(nod != node);
        C.push_back(con);
    }
}
void write()
{
    cout << C.size() << "\n";
    for(vector< vector<int> > :: iterator it =  C.begin(); it != C.end(); ++ it)
    {
        //cout << it->size() << " ";
        for( vector<int> :: iterator it2 = it->begin(); it2 != it->end(); ++ it2)
            cout << *it2 << " " ;
        cout << "\n";
    }
}