Pagini recente » Cod sursa (job #2230158) | Cod sursa (job #2147045) | Cod sursa (job #542565) | Cod sursa (job #2932592) | Cod sursa (job #3030761)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
using VI = vector<int>;
using VB = vector<bool>;
using VVI = vector<VI>;
using SI = set<int>;
using SSI = set<SI>;
int indx, n, m;
VB v, inStack;
VI index, low;
VVI G;
SI cc;
SSI ctc;
stack<int>stk;
int extract(int x)
{
cc.clear();
while(!stk.empty())
{
int node = stk.top();
stk.pop();
inStack[node] = 0;
cc.insert(node);
if (node == x)
break;
}
ctc.insert(cc);
}
void dfs(int x)
{
v[x] = 1;
stk.push(x);
index[x] = low[x] = ++ indx;
inStack[x] = 1;
for (const int& y : G[x])
{
if (!v[y]) {
dfs(y);
low[x] = min(low[y], low[x]);
}
else if (inStack[y])
low[x] = min(index[y], low[x]);
}
if (index[x] == low[x])
extract(x);
}
void afis()
{
fout << ctc.size() << '\n';
for (auto cc : ctc) {
for (int j : cc)
fout << j << ' ';
fout << '\n';
}
}
void Tarjan()
{
for (int node = 1; node <= n; ++node)
if (!v[node])
dfs(node);
}
int main()
{
fin >> n >> m;
int x, y;
G = VVI(n + 1);
v = VB(n + 1);
inStack = VB(n + 1);
index = low = VI(n + 1);
for (int i = 1; i <= m; ++i)
{
fin >> x >> y;
G[x].push_back(y);
}
Tarjan();
afis();
return 0;
}