Pagini recente » Cod sursa (job #816834) | Monitorul de evaluare | Cod sursa (job #1879480) | Cod sursa (job #1919103) | Cod sursa (job #2719685)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100005;
int n, m;
vector<bool>viz(NMAX);
vector<int>G[NMAX];
vector<int>Gt[NMAX];
vector<vector<int> >sol;
vector<int>c;
stack<int>st;
void dfs(int u)
{
viz[u] = true;
for (int v : G[u])
if (!viz[v])
dfs(v);
st.push(u);
}
void dfsT(int u)
{
viz[u] = true;
for (int v : Gt[u])
if (!viz[v])
dfsT(v);
c.push_back(u);
}
void read()
{
fin >> n >> m;
while (m--)
{
int a, b;
fin >> a >> b;
G[a].push_back(b);
Gt[b].push_back(a);
}
}
void solve()
{
viz.assign(n + 5, 0);
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i);
viz.assign(n + 5, 0);
while (!st.empty())
{
int u = st.top();
st.pop();
c.clear();
if (viz[u]) continue;
dfsT(u);
sol.push_back(c);
}
fout << sol.size() << '\n';
for (int i = 0; i < sol.size(); i++)
{
sort(sol[i].begin(), sol[i].end());
for (int e : sol[i])
fout << e << ' ';
fout << '\n';
}
}
int main()
{
read();
solve();
return 0;
}