Pagini recente » Cod sursa (job #460013) | Istoria paginii runda/sibiu_contest_oni | Rezultatele filtrării | Cod sursa (job #1701195) | Cod sursa (job #3302751)
#include <bits/stdc++.h>
using namespace std;
vector<int> v1[100005], v2[100005];
int depth[100005];
int ord[100005];
int idx;
vector<int> comp[100005];
void dfs1(int node)
{
for(auto &son : v1[node])
if(!depth[son])
{
depth[son] = depth[node] + 1;
dfs1(son);
}
ord[++idx] = node;
}
void dfs2(int node, int color)
{
for(auto &son : v2[node])
if(!depth[son])
{
depth[son] = depth[node];
dfs2(son, color);
}
}
signed main()
{
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
int n, m; fin>>n>>m;
while(m--)
{
int a, b; fin>>a>>b;
if(a == b) continue;
v1[a].push_back(b);
v2[b].push_back(a);
}
for(int i=1; i<=n; ++i)
if(!depth[i])
{
depth[i] = 1;
dfs1(i);
}
reverse(ord+1, ord+n+1);
for(int i=1; i<=n; ++i)
depth[i] = 0;
int color = 0;
for(int i=1; i<=n; ++i)
if(!depth[ord[i]])
{
depth[ord[i]] = ++color;
dfs2(ord[i], color);
comp[color].push_back(ord[i]);
}
else
comp[depth[ord[i]]].push_back(ord[i]);
fout<<color<<'\n';
for(int i=1; i<=color; ++i, fout<<'\n')
for(auto &j : comp[i])
fout<<j<<' ';
return 0;
}