Cod sursa(job #2968292)

Utilizator DianaZaharia132nr2Zaharia Diana Cristiana DianaZaharia132nr2 Data 20 ianuarie 2023 21:35:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

int n, m, x, y, viz[100001], validnds[100001], mintime[100001], min_nd[100001], cnt = 1, ctcnr, stv_top;
vector <vector<int>> lst,ctc;
stack <int> stv;

ifstream f("ctc.in");
ofstream g("ctc.out");

void DFS(int curnd){

 viz[curnd] = 1;
 cnt ++;
 mintime[curnd] = cnt;
 min_nd[curnd] = cnt;
 validnds[curnd] = 1;
 stv.push(curnd);


 for(auto vcnd : lst[curnd]){

     if(viz[vcnd] && validnds[vcnd])
         min_nd[curnd] = min(min_nd[curnd], mintime[vcnd]);

     else if (!viz[vcnd]){

         DFS(vcnd);
         if(validnds[vcnd])
             min_nd[curnd] = min(min_nd[vcnd], min_nd[curnd]);

        }

    }

 if(mintime[curnd] == min_nd[curnd]){
     ctcnr ++;
    while(true){

        stv_top = stv.top();
        stv.pop();
        validnds[stv_top] = 0;
        ctc[ctcnr].push_back(stv_top);
        if(stv_top == curnd)
            break;

    }
 }

}

int main(){

    f >> n >> m;
    lst.assign(n + 1, vector<int>());
    for (int i=1; i<=m; i++){

        f >> x >> y;
        lst[x].push_back(y);

    }

    ctc.assign(n + 1, vector<int>());

    for(int i=1; i<=n; i++)
      if(!viz[i])
         DFS(i);

    g << ctcnr;

    for (auto comp : ctc){
      for (auto nod : comp)
        g << nod << " ";
      g << "\n";
    }

 return 0;

 f.close();
 g.close();

}