Cod sursa(job #2298575)

Utilizator iarinatudorTudor Iarina Maria iarinatudor Data 8 decembrie 2018 11:30:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack <int> S;
int ix[100010],llx[100010],ok[100010];
int nr=0;
vector <int> G[100010];
vector <int> Sol[100010];
int n,m,index=1;
void citire()
{
    int x, y;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
    }
}
void tarjan(int v)
{
   ix[v]=index;
   llx[v]=index;
   index++;
   S.push(v);
   ok[v]=1;
   for(auto &x:G[v])
   {
       if(ix[x]==0)
       {
           tarjan(x);
           llx[v]=min(llx[v],llx[x]);
       }
       else if(ok[x])
       {
          llx[v]=min(llx[v],ix[x]);
       }
   }
    if(llx[v]==ix[v])
    {   nr++;
        while(!S.empty()&&S.top()!=v)
        {
            Sol[nr].push_back(S.top());
            ok[S.top()]=0;
            S.pop();
        }
        if(!S.empty())
        {
            Sol[nr].push_back(S.top());
            ok[S.top()]=0;
            S.pop();
        }

    }

}

int main()
{
    citire();
    for(int i=1; i<=n; i++)
    {
        if(ix[i]==0)
            tarjan(i);
    }
    fout<<nr<<"\n";
    for(int i=1; i<=nr; i++)
    {
        for(auto &vf: Sol[i])
            fout<<vf<<" ";
        fout<<"\n";
    }

    return 0;
}