Pagini recente » Cod sursa (job #2619649) | Cod sursa (job #1901851) | Cod sursa (job #1876444) | Cod sursa (job #1057434) | Cod sursa (job #3030717)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
using VI = vector<int>;
using VB = vector<bool>;
using VVI = vector<VI>;
int indx, n, m;
VB v, inStack;
VI index, low;
VVI G;
set<int> cc;
set<set<int> > 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 (auto 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()
{
cout << ctc.size() << '\n';
for (auto cc : ctc) {
for (auto j : cc)
cout << j << ' ';
cout << '\n';
}
}
int main()
{
cin >> 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)
{
cin >> x >> y;
G[x].push_back(y);
}
for (int i = 1; i <= n; ++i)
if (!v[i])
dfs(i);
afis();
return 0;
}