Cod sursa(job #1336253)

Utilizator armandpredaPreda Armand armandpreda Data 7 februarie 2015 13:03:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int LIM=100003;
int n,id[LIM],low[LIM],nx,nc;
vector <int> gr[LIM];
stack <int> s,afis;
bitset <LIM> ins;
void tarjan(int nod)
{
    s.push(nod);
    nx++;
    id[nod]=nx;
    low[nod]=nx;
    ins[nod]=1;
    for(int i=0;i<gr[nod].size();++i)
        if(id[gr[nod][i]]==0)
        {
            tarjan(gr[nod][i]);
            low[nod]=min(low[nod],low[gr[nod][i]]);
        }
        else
            if(ins[gr[nod][i]])
                low[nod]=min(low[nod],low[gr[nod][i]]);
    if(id[nod]==low[nod])
    {
        nc++;
        do
        {
            afis.push(s.top());
            ins[s.top()]=0;
            s.pop();
        }while(nod!=afis.top());
    }
}
int main()
{
    int m;
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        fin>>x>>y;
        gr[x].push_back(y);
    }
    for(int i=1;i<=n;++i)
        if(id[i]==0)
            tarjan(i);
    fout<<nc;
    while(!afis.empty())
    {
        if(id[afis.top()]==low[afis.top()]) fout<<"\n";
        fout<<afis.top()<<" ";
        afis.pop();
    }
    return 0;
}