Cod sursa(job #973326)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 14 iulie 2013 10:54:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>
#include <set>
#include <stack>
#define add push_back
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int MAXN = 100005;
const int oo = (1<<31)-1;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

Graph G;
int N, M, deep;
vector<int> Lowlink(MAXN), Deep(MAXN);
stack<int> Stack;
set< set<int> > StronglyConnectedComponents;
bitset<MAXN> in_Stack;

inline void Get_min(int &a, int b){
    if(a>b)
        a=b;
}

void ReadData(){
    cin >> N >> M;
    for(int i = 1 ; i <= M ; ++ i){
        int X, Y;
        cin >> X >> Y;
        G[X].add(Y);
    }
}

void WriteData(){
    cout << StronglyConnectedComponents.size() << "\n";
    for(set<set<int> > :: iterator it = StronglyConnectedComponents.begin(), fin = StronglyConnectedComponents.end() ; it != fin ; ++ it, cout << "\n")
        for(set<int> :: iterator jt = it->begin() , jin = it->end() ; jt != jin ; ++ jt)
            cout << *jt << " ";
}

void Tarjan(int Node){
    Deep[Node] = Lowlink[Node] = ++deep;
    Stack.push(Node);
    in_Stack[Node] = true;
    for(It it = G[Node].begin(), fin = G[Node].end() ; it != fin ; ++ it)
        if(!Deep[*it]){
            Tarjan(*it);
            Get_min(Lowlink[Node], Lowlink[*it]);
        }
        else if(in_Stack[*it])
            Get_min(Lowlink[Node], Lowlink[*it]);
    if(Lowlink[Node] == Deep[Node]){
        set<int> CurrentComponent;
        int Nod;
        do{
            CurrentComponent.insert(Nod = Stack.top());
            Stack.pop();
            in_Stack[Nod] = false;
        }while(Nod != Node);
        StronglyConnectedComponents.insert(CurrentComponent);
    }
}

void StartSolving(){
    for(int i = 1 ; i <= N ; ++ i)
        if(!Deep[i])
            Tarjan(i);
}

int main()
{
    ReadData();
    StartSolving();
    WriteData();
    cin.close();
    cout.close();
    return 0;
}