Pagini recente » Cod sursa (job #3311082) | Cod sursa (job #3340142) | Cod sursa (job #3345378) | Cod sursa (job #3315069) | Cod sursa (job #3344946)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int maxn = 1e5+1;
vector<int> graph[maxn], Tgraph[maxn], edge[maxn];
vector<int> topsort, fr(maxn);
int n, m;
void dfs( int node )
{
fr[node] = 1;
for( auto adj : graph[node] )
{
if( fr[adj] == 0 )
{
dfs(adj);
}
}
topsort.push_back(node);
}
vector<int> component;
void dfs2( int node )
{
fr[node] = 1;
component.push_back(node);
for( auto adj : Tgraph[node] )
{
if( fr[adj] == 0 )
{
dfs2(adj);
}
}
}
int main()
{
ios::sync_with_stdio(false);f.tie(nullptr);g.tie(nullptr);
f >> n >> m;
for( int i = 1; i <= n; ++i )
fr[i] = 0;
for( int i = 1; i <= m; ++i )
{
int a, b;
f >> a >> b;
graph[a].push_back(b);
Tgraph[b].push_back(a);
}
for( int i = 1; i <= n; ++i )
{
if( fr[i] == 0 )
dfs(i);
}
for( int i = 1; i <= n; ++i )
fr[i] = 0;
vector<vector<int>> ans;
int cnt = -1;
for( int i = topsort.size()-1; i >= 0; --i )
{
int node = topsort[i];
if( fr[node] == 0 )
{
++cnt;
ans.push_back({});
component.clear();
dfs2(node);
for( int j = 0; j < component.size(); ++j )
{
ans[cnt].push_back( component[j] );
}
}
}
g << ans.size() << "\n";
for( int i = 0; i < ans.size(); ++i )
{
for( auto j : ans[i] )
g << j << " ";
g << "\n";
}
return 0;
}