Pagini recente » Cod sursa (job #484412) | Cod sursa (job #1626257) | Cod sursa (job #1601109) | Cod sursa (job #1434410) | Cod sursa (job #2958668)
#include <fstream>
#include <set>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("cbc.in");
ofstream fout("cbc.out");
using SI = set<int>;
using VI = vector<int>;
using VVI = vector<VI>;
using SSI = set<SI>;
using VB = vector<bool>;
VVI G;
VB V, inStack;
SI C; // comp. curenta
SSI CTC; //
VI index, low;
int idx;
stack<int> stk;
int n, m;
void ReadData();
void Tarjan();
void Extract_CBC(int x);
void Print_CBC();
int main(){
ReadData();
Tarjan();
Print_CBC();
return 0;
}
void Print_CBC(){
fout << CTC.size() << '\n';
for (auto const& comp : CTC){
for (auto const& node : comp)
fout << node << ' ';
fout << '\n';
}
}
void Extract_CBC(int x){
C.clear();
while (!stk.empty()){
int node = stk.top();
stk.pop();
inStack[node] = false;
C.insert(node);
if (node == x)
break;
}
CTC.insert(C);
}
void DF(int x){
V[x] = true;
index[x] = low[x] = ++idx;
stk.emplace(x);
inStack[x] = true;
for (auto const& y : G[x])
if (!V[y]){ // daca y este fiul lui x;
DF(y);
low[x] = min(low[x], low[y]);
}
else
if(inStack[y]) // daca y este stramos al lui x
low[x] = min(low[x], index[y]);
if (index[x] == low[x]){ // daca x este tatal unei noi C.T.C.
Extract_CBC(x);
}
}
void Tarjan(){
for (int node = 1; node <= n; ++node){
if (!V[node])
DF(node);
}
}
void ReadData(){
fin >> n >> m;
G = VVI(n + 1);
V = inStack = VB(n + 1);
index = low = VI(n + 1);
int x, y;
while (m--){
fin >> x >> y;
G[x].emplace_back(y);
}
}