Cod sursa(job #2923797)

Utilizator MohneaGosuMihnea Gusu MohneaGosu Data 19 septembrie 2022 11:33:50
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
const int N=1e5 +5;
const int M=2e5 +5;
const int inf=1e9;
int index1[N];
int indexcur;
int indexmax[N];
bool instiva[N];
bool procesat[N];
vector <int> v[N];
int n,m;
vector <int> tc[N];
int compcur;
vector <int> stiva;
void f1(int nod)
{
    if (!instiva[nod] && !procesat[nod]){
        stiva.push_back(nod);
        instiva[nod]=1;
        procesat[nod]=1;
        index1[nod]=indexcur;
        indexcur++;
        indexmax[nod]=index1[nod];
        for (int i=0;i<v[nod].size();i++){
            f1(v[nod][i]);

            if (instiva[v[nod][i]] && indexmax[v[nod][i]]<indexmax[nod]){
                indexmax[nod]=indexmax[v[nod][i]];
            }
        }
        if (index1[nod]==indexmax[nod]){
            while(stiva.back()!=nod){
                tc[compcur].push_back(stiva.back());
                stiva.pop_back();
                instiva[stiva.back()]=0;
            }
            stiva.pop_back();
            tc[compcur].push_back(nod);
            instiva[nod]=0;
            compcur++;
        }

    }
}
int main()
{
    in>>n>>m;
    for (int i=0;i<m;i++){
        int x,y;
        in>>x>>y;
        v[x].push_back(y);
    }
    f1(1);
    out<<compcur<<"\n";
    for (int i=0;i<compcur;i++){
        for (int j=0;j<tc[i].size();j++){
            out<<tc[i][j]<<" ";
        }
        out<<"\n";
    }
    return 0;
}