Pagini recente » Cod sursa (job #759418) | Cod sursa (job #1444987) | Cod sursa (job #1630032) | Cod sursa (job #98832) | Cod sursa (job #1915552)
#include <fstream>
#include <vector>
#include <stack>
#define NMax 100010
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int nodes, edges, preord[NMax], low[NMax], scc;
bool mark[NMax], inStack[NMax];
vector<int> G[NMax], answ[NMax];
stack<int> crtNodes;
int get_min(int a, int b)
{
if (a < b)
return a;
return b;
}
void Tarjan(int node)
{
mark[node] = true;
preord[node] = ++preord[0];
low[node] = preord[node];
crtNodes.push(node);
inStack[node] = true;
for (auto& crt : G[node]) {
if (!mark[crt]) {
Tarjan(crt);
low[node] = get_min(low[node], get_min(preord[node], low[crt]));
}
else if (inStack[crt])
low[node] = get_min(low[node], get_min(preord[node], low[crt]));
}
if (preord[node] == low[node]) {
scc++;
while (crtNodes.top() != node) {
int crt = crtNodes.top();
answ[scc].push_back(crt);
crtNodes.pop();
inStack[crt] = false;
}
answ[scc].push_back(node);
crtNodes.pop();
inStack[node] = false;
}
}
int main()
{
f >> nodes >> edges;
int n1, n2;
for (int i = 1; i <= edges; i++) {
f >> n1 >> n2;
G[n1].push_back(n2);
}
Tarjan(1);
g << scc << '\n';
for (int i = 1; i <= scc; i++) {
for (auto& a : answ[i])
g << a << ' ';
g << '\n';
}
}