Pagini recente » Cod sursa (job #91385) | Cod sursa (job #2052862) | Cod sursa (job #2406397) | Cod sursa (job #755150) | Cod sursa (job #2842748)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<vector<int>> solutie;
void DFS_CTC(int nod_curent,vector<vector<int>> lv, vector<int> &descoperit, vector<int> &low, stack<int> &stiva, vector<bool> &membruStiva, int &nr){
static int timp = 0;
descoperit[nod_curent] = low[nod_curent] = timp++;
stiva.push(nod_curent);
membruStiva[nod_curent] = true;
for (auto elem: lv[nod_curent]){
if (descoperit[elem] == -1){
DFS_CTC(elem, lv, descoperit, low, stiva, membruStiva, nr);
low[nod_curent] = min(low[nod_curent],low[elem]);
}
else if(membruStiva[elem] == true){
low[nod_curent] = min(low[nod_curent], descoperit[elem]);
}
}
if (descoperit[nod_curent] == low[nod_curent]){
vector<int> aux;
solutie.push_back(aux);
for (int nod = stiva.top(); nod != nod_curent; nod = stiva.top()){
stiva.pop();
membruStiva[nod] = false;
solutie[nr].push_back(nod);
}
int nod = stiva.top();
stiva.pop();
membruStiva[nod] = false;
solutie[nr].push_back(nod);
nr++;
}
}
void CTC(vector<vector<int>> lv){
vector<int> descoperit(lv.size(), -1); // timpul de descoperire in dfs
vector<int> low(lv.size(), -1); // minimul timpului de descoperire pentru nod
stack<int> stiva;
vector<bool> membruStiva(lv.size(), false);
int nr = 0; // numarul componenetelor tare conexe
// daca nodul nu a fost descoperit
for (int i = 0; i < lv.size(); i++){
if (descoperit[i] == -1)
DFS_CTC(i, lv, descoperit, low, stiva, membruStiva, nr);
}
g << nr << "\n";
for (auto elem : solutie){
for (auto x : elem){
g << x << " ";
}
g << "\n";
}
}
int main(){
int n, m, nod1, nod2;
f >> n >> m;
vector<vector<int>> lv;
for (int i = 0; i < n; i++){
vector<int> aux;
lv.push_back(aux);
}
for (int i = 0; i < m; i++){
f >> nod1;
f >> nod2;
lv[nod1 - 1].push_back(nod2 - 1);
}
CTC(lv);
return 0;
}