Cod sursa(job #755771)

Utilizator BitOneSAlexandru BitOne Data 6 iunie 2012 22:44:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stack>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
const int N_MAX=100011;

stack<int> S;
vector<int> G[N_MAX], CTC[N_MAX];
int index, ctcSize;
bool isInStack[N_MAX];
int lowIndex[N_MAX], dfsIndex[N_MAX];

inline int _min(int x, int y) {return x <= y ? x : y;}
inline void DFS(int x)
{
    S.push(x);
    isInStack[x]=true;
    lowIndex[x]=dfsIndex[x]=++index;
    vector<int>::const_iterator it=G[x].begin(), iend=G[x].end();

    for(; it < iend; ++it)
        if(0 == dfsIndex[*it])
        {
            DFS(*it);
            lowIndex[x]=_min(lowIndex[x], lowIndex[*it]);
        }
        else if(true == isInStack[*it] && lowIndex[x] > lowIndex[*it])
                lowIndex[x]=lowIndex[*it];
    if(dfsIndex[x] == lowIndex[x])
    {
        static int y;
        do {
                y=S.top(); S.pop();
                isInStack[y]=false;
                CTC[ctcSize].push_back(y);
           }while(x != y);
        ++ctcSize;
    }
}
int main()
{
    int N, M, x, y, i;
    ifstream in("ctc.in");
    ofstream out("ctc.out");

    for(in>>N>>M; M; --M)
    {
        in>>x>>y;
        G[x].push_back(y);
    }
    for(x=1; x <= N; ++x)
        if(0 == dfsIndex[x])
            DFS(x);
    out<<ctcSize<<'\n';
    for(i=0; i < ctcSize; ++i)
    {
        copy(CTC[i].begin(), CTC[i].end(), ostream_iterator<int>(out, " "));
        out<<'\n';
    }

    return EXIT_SUCCESS;
}