Cod sursa(job #848047)

Utilizator IoannaPandele Ioana Ioanna Data 4 ianuarie 2013 19:15:54
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<fstream>
#include<bitset>
#include<vector>
#include<stack>
#define NMAX 100002
#define MMAX 200002

using namespace std;

int n,m,nr;
int lowl[NMAX],level[NMAX];
vector <int> v[NMAX],comp[NMAX];
stack <int> S;
bitset <NMAX> viz;

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

void scan() {

    int a,b;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        in>>a>>b;
        v[a].push_back(b);
    }
}

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

void componenta(int nod)
{
    int a;
    nr++;
    while (S.top()!=nod)
    {
        a=S.top();
        comp[nr].push_back(a);
        viz[a]=false;
        S.pop();

    }
    comp[nr].push_back(nod);
    viz[nod]=false;
    S.pop();

}
void dfs(int nod,int nivel)
{
    level[nod]=nivel;
    lowl[nod]=nivel;
    viz[nod]=true;
    S.push(nod);
    for (vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++)
    {
        if (!level[*it])
        {
            dfs(*it,nivel+1);
            lowl[nod]=min(lowl[nod],lowl[*it]);
        }
        else if (viz[*it]==true)
                lowl[nod]=min(lowl[nod],lowl[*it]);
    }
    if (lowl[nod]==level[nod])
        componenta(nod);

}

void print()
{
    out<<nr<<"\n";
    for (int i=1;i<=nr;i++)
    {
        for (vector<int>::iterator it=comp[i].end()-1;it>=comp[i].begin();it--)
            out<<*it<<" ";
        out<<"\n";
    }
}

int main() {

    scan();
    for (int i=1;i<=n;i++)
    {

        if (!level[i]) dfs(i,1);
    }
    print();
    return 0;
}