Cod sursa(job #1468778)

Utilizator horiainfoTurcuman Horia horiainfo Data 6 august 2015 22:36:08
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 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];
int nrComp, check,n,m, nod1, nod2;
stack<int> stiva;

void DFS(int nod,int level)
{
    viz[nod] = check; retLv[nod] = level;
    stiva.push(nod);
    for(int i=0;i<G[nod].size();i++)
        if(viz[G[nod][i]] == 0)
        {
            DFS(G[nod][i],level+1);
            if(retLv[G[nod][i]] < retLv[nod])
                retLv[nod] = retLv[G[nod][i]];
        }
        else
            if(viz[G[nod][i]] == check)
            {
                if(retLv[G[nod][i]] < retLv[nod])
                    retLv[nod] = retLv[G[nod][i]];
            }
    if(retLv[nod] == level)
    {
        nrComp ++;
        while(stiva.top() != nod)
        {
            co[nrComp].push_back(stiva.top());
            stiva.pop();
        }
        co[nrComp].push_back(nod);
        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++;
            DFS(i,1);
        }

    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;
}