Cod sursa(job #880868)

Utilizator ericptsStavarache Petru Eric ericpts Data 17 februarie 2013 14:12:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>

using namespace std;

#define forEach(G) for(typeof (G).begin() it = (G).begin(); it != (G).end(); ++it)

#define pb push_back

#define maxn 100005

#define cout out

int n,m;
vector<int> graf[maxn];
vector< vector<int> > comp;
int index[maxn];
int lowest[maxn];
int cr;
bool good[maxn];
stack<int> S;
ifstream in("ctc.in");
ofstream out("ctc.out");

void read()
{
    int a,b;
    in >> n >> m;
    while(m--)
    {
        in >> a >> b;
        graf[a].push_back(b);
    }
}

void dfs(int nod)
{
    index[nod] = ++cr;
    lowest[nod] = cr;
    S.push(nod);
    good[nod]=1;
    forEach(graf[nod])
    {
        if(!lowest[*it])
            dfs(*it);
        if(good[*it])
            lowest[nod] = min(lowest[nod],lowest[*it]);
    }
    if(index[nod] == lowest[nod])
    {
        vector<int> dat;
        int x;
        do
        {
            x = S.top();
            S.pop();
            dat.pb(x);
            good[x]=0;
        }
        while(x != nod);
        comp.pb(dat);
    }
}

void print()
{
    cout << comp.size() << "\n";
    int i;
    for(i=0;i<comp.size();++i)
    {
        forEach(comp[i])
            cout << *it << " ";
        cout << "\n";
    }
}

int main()
{
    read();
    int i;
    for(i=1;i<=n;++i)
        if(!index[i])
            dfs(i);
    print();
    return 0;
}