Pagini recente » telefon3 | Cod sursa (job #513044) | Cod sursa (job #3284484) | Magazin | Cod sursa (job #2702387)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector<vector<int>> v, tv, rez;
stack<int> st;
vector<bool> bif;
void dfs1(int);
void dfs2(int);
int main()
{
f >> n >> m;
bif.resize(n + 1);
v.resize(n + 1);
tv.resize(n + 1);
for (int x, y; m; m--)
f >> x >> y, v[x].emplace_back(y), tv[y].emplace_back(x);
for (int i = 1; i <= n; i++)
if (!bif[i])
dfs1(i);
while (!st.empty())
{
int ac = st.top();
st.pop();
if (bif[ac])
rez.emplace_back(vector<int>()), dfs2(ac);
}
g << rez.size() << '\n';
for (const auto &i : rez)
{
for (const auto &j : i)
g << j << " ";
g << '\n';
}
return 0;
}
void dfs1(int x)
{
bif[x] = 1;
for (const auto &i : v[x])
if (!bif[i])
dfs1(i);
st.push(x);
}
void dfs2(int x)
{
bif[x] = 0;
rez.back().emplace_back(x);
for (const auto &i : tv[x])
if (bif[i])
dfs2(i);
}