Pagini recente » Cod sursa (job #677410) | Cod sursa (job #1715369) | Cod sursa (job #2887485) | Cod sursa (job #2313184) | Cod sursa (job #2204529)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N_MAX = 1e5;
int n, m;
vector<int> gr[N_MAX + 2], grt[N_MAX + 2];
int num;
int ord[2][N_MAX + 2];
bool vis[N_MAX + 2];
int daddy[N_MAX + 2], depth[N_MAX + 2];
int find(int node);
void join(int r1, int r2);
vector<int> ans[N_MAX + 2];
void dfs1(int node)
{
vis[node] = true;
for(auto it: gr[node])
if(!vis[it])
dfs1(it);
num++;
ord[0][node] = num;
ord[1][num] = node;
}
void dfs2(int node)
{
vis[node] = true;
for(auto it: grt[node])
if(!vis[it])
{
if(ord[0][daddy[node]] > ord[0][daddy[it]])
join(find(it), find(node));
dfs2(it);
}
}
int main()
{
in >> n >> m;
while(m--)
{
int x, y;
in >> x >> y;
gr[x].push_back(y);
grt[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(!vis[i])
dfs1(i);
for(int i = 1; i <= n; i++)
{
vis[i] = 0;
daddy[i] = i;
depth[i] = 1;
}
for(int i = n; i >= 1; i--)
if(!vis[ord[1][i]])
dfs2(ord[1][i]);
int nr = 0;
for(int i = 1; i <= n; i++)
{
int val = find(i);
ans[val].push_back(i);
if(ans[val].size() == 1)
nr++;
}
out << nr << '\n';
for(int i = 1; i <= n; i++)
if(ans[i].size())
{
for(auto it: ans[i])
out << it << ' ';
out << '\n';
}
return 0;
}
int find(int node)
{
int r = daddy[node];
while(daddy[r] != r)
r = daddy[r];
return r;
}
void join(int r1, int r2)
{
if(depth[r1] == depth[r2])
{
daddy[r1] = r2;
depth[r2]++;
}
else if(depth[r1] > depth[r2])
daddy[r2] = r1;
else
daddy[r1] = r2;
}