Cod sursa(job #1468781)

Utilizator horiainfoTurcuman Horia horiainfo Data 6 august 2015 23:01:17
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>

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

vector<int> G[100002],co[100001];
int viz[100001], retLv[100002];
bool inStack[100002];
int nrComp, check,n,m, nod1, nod2, level;
stack<int> stiva;

void DFS(int nod)
{
    int mylevel = ++level;
    viz[nod] = check; retLv[nod] = level;
    stiva.push(nod); inStack[nod] = 1;
    for(int i=0;i<G[nod].size();i++)
        if(viz[G[nod][i]] == 0)
        {
            DFS(G[nod][i]);
            if(retLv[G[nod][i]] < retLv[nod])
                retLv[nod] = retLv[G[nod][i]];
        }
        else
            if(viz[G[nod][i]] == check && inStack[G[nod][i]])
            {
                if(retLv[G[nod][i]] < retLv[nod])
                    retLv[nod] = retLv[G[nod][i]];
            }
    if(retLv[nod] == mylevel)
    {
        nrComp ++;
        while(stiva.top() != nod)
        {
            co[nrComp].push_back(stiva.top());
            inStack[stiva.top()] = 0;
            stiva.pop();
        }
        co[nrComp].push_back(nod);
        inStack[nod] = 0;
        stiva.pop();
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>nod1>>nod2;
        G[nod1].push_back(nod2);
    }

    for(int i=1;i<=n;i++)
        if(viz[i]==0)
        {
            check++;
            level = 0;
            DFS(i);
        }

    fout<<nrComp<<'\n';
    for(int i=1;i<=nrComp;i++)
    {
        sort(co[i].begin(),co[i].end());
        for(int j=0;j<co[i].size();j++)
            fout<<co[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}