Cod sursa(job #1905586)

Utilizator marcdariaDaria Marc marcdaria Data 6 martie 2017 09:29:46
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;

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

const int MaxN=100005;
int N,M;
vector<int> G[MaxN], c;
vector<vector<int>> cc;
int d[MaxN], low[MaxN];
int deep;
bitset<MaxN> inStack;
stack<int> St;

void Read();
void Tarjan(int x);

int main()
{
    Read();
    for(int i=1;i<=N;++i)
        if(!d[i])
        Tarjan(i);

    fout<<cc.size()<<'\n';

    for(const auto& y : cc)
    {
        for(const int & x : y)
            fout<<x<<" ";
        fout<<'\n';
    }

    return 0;
}

void Read()
{
    fin>>N>>M;
    while(M--)
    {
        int x,y;
        fin>>x>>y;
        G[x].push_back(y);
    }
    fin.close();
}
void Tarjan(int x)
{
    d[x]=low[x]=deep++;
    St.push(x);
    inStack[x]=true;

    for(const int& y : G[x])
    {
        if(!d[y])
        {
            Tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(inStack[y])
            low[x]=min(low[x],d[y]);


        if(d[x]==low[x])
        {
            c.clear();
            int x2;
            while(true)
            {
                c.push_back(x2=St.top());
                St.pop();
                inStack[x2]=false;
                if(x2==x)
                    break;
            }
        }
    }

    cc.push_back(c);
}