Pagini recente » Borderou de evaluare (job #774175) | Borderou de evaluare (job #1123076) | Borderou de evaluare (job #151488) | Borderou de evaluare (job #2003294) | Cod sursa (job #2960522)
// 13 PM
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
using VI = vector<int>;
using VB = vector<bool>;
using VVI = vector<VI>;
VVI G; // the graph
VI c; // current component
VVI ctc; // stores all components
VB P; // P[x] = true if the node x is visited
VB InStack; // InStack[x] = true if the node x is currently in Stack
VI indexx, low_index; // stores the index and the low index of all nodes
stack<int> stk;
int n, m;
int idx;
void ReadGraph();
void Tarjan();
void DF(int x);
void Extract_comp(int x);
void Print_comp();
int main(){
ReadGraph();
Tarjan();
Print_comp();
return 0;
}
void Print_comp(){
fout << ctc.size() << '\n';
for (auto const& C : ctc)
{
for (auto const& node : C)
fout << node << ' ';
fout << '\n';
}
}
void DF(int x){
P[x] = true;
indexx[x] = low_index[x] = ++idx;
stk.emplace(x);
InStack[x] = true;
for (int const& y : G[x])
if (!P[y]){ // daca y este fiul lui x
DF(y);
low_index[x] = min(low_index[x], low_index[y]);
}
else
if (InStack[y]) // daca y este stramos al lui x (x -> y == back edge)
low_index[x] = min(low_index[x], indexx[y]);
if (indexx[x] == low_index[x]) // if x is the representant of a new component
Extract_comp(x);
}
void Extract_comp(int x){
c.clear(); // clear the vector for a new component
while (!stk.empty()){
int node = stk.top();
stk.pop();
InStack[node] = false;
c.push_back(node);
if (node == x) // if all the nodes of the component have been stored
break;
}
ctc.emplace_back(c);
}
void Tarjan(){
for (int node = 1; node <= n; ++node)
if (!P[node])
DF(node);
}
void ReadGraph(){
fin >> n >> m;
G = VVI(n + 1); // initializations
low_index = VI(n + 1);
indexx = VI(n + 1);
P = InStack = VB(n + 1);
int x, y;
while (m--){
fin >> x >> y;
G[x].emplace_back(y);
}
}