Pagini recente » Cod sursa (job #805847) | Cod sursa (job #2147991) | Cod sursa (job #582208) | Cod sursa (job #3153089) | Cod sursa (job #2832576)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N;
int M;
int start;
vector<vector<int>> vecini;
void citire_graf() {
f >> N;
f >> M;
int nod1, nod2;
vecini.resize(N + 1);
for (int i = 0; i < M; i++) {
f >> nod1 >> nod2;
vecini[nod1].push_back(nod2);
}
}
void DFS_CTC(vector<bool>& inStiva, int fiu, vector<int>& nivel, vector<int>& low, stack<int>& stack, vector<vector<int>>& compConexe, int& nrCC, int &dist) {
nivel[fiu] = low[fiu] = dist;
dist=dist+1;
stack.push(fiu);
inStiva[fiu] = true;
int i;
for (i = 0; i < vecini[fiu].size(); i++)
{
if (nivel[vecini[fiu][i]] == -1) {//nevizitat
DFS_CTC(inStiva, vecini[fiu][i], nivel, low, stack, compConexe, nrCC, dist);
low[fiu] = min(low[fiu], low[vecini[fiu][i]]);
}
else if (inStiva[vecini[fiu][i]] == true) {//daca e in stiva
low[fiu] = min(low[fiu], nivel[vecini[fiu][i]]);
}
}
if (low[fiu]== nivel[fiu]) {//cand nivel fiu ajunge egal cu low de fiu,avem nod radacina
//incepem componenta tare conexa
int node = stack.top();
stack.pop();
inStiva[node] = false;
compConexe[nrCC].push_back(node);
while (node != fiu)
{
node = stack.top();
stack.pop();
inStiva[node] = false;
compConexe[nrCC].push_back(node);
}
nrCC++;
}
}
void CTC_init_si_print() {
vector<bool> inStiva(N+1 , false);
vector<int> nivel(N+1);//vector de nivele
vector<int> low(N+1);//vector de low level pentru fiecare nod
stack<int> stack; //stiva cu nodurile vizitate
vector<vector<int>> compConexe;
compConexe.resize(N+1);
int nrCC = 0;
int dist = 0;
// Initialize disc and low, and stackMember arrays
for (int i = 1; i <= N; i++)
{
nivel[i] = -1;
low[i] = -1;
inStiva[i] = false;
}
for (int i = 1; i <= N; i++)
if (nivel[i] == -1)
DFS_CTC(inStiva, i, nivel, low, stack, compConexe, nrCC, dist);
g << nrCC << '\n';
for (int i = 0; i < nrCC; i++) {
for (int j = 0; j < compConexe[i].size(); j++)
g << compConexe[i][j] << " ";
g << '\n';
}
}
int main()
{
citire_graf();
CTC_init_si_print();
return 0;
}