Pagini recente » Cod sursa (job #2991303) | Cod sursa (job #3173308) | Cod sursa (job #2563777) | Cod sursa (job #2887636) | Cod sursa (job #3243160)
#include <bits/stdc++.h>
using namespace std;
int visited[100001];
vector<vector<int>>adj;
vector<vector<int>>ans;
vector<vector<int>>adj_rev;
void dfs(int x,vector<int>&auxv, vector<vector<int>>&adjaux)
{
visited[x]=1;
for(int i = 0; i < adjaux[x].size(); i++)
{
if(!visited[adjaux[x][i]])
dfs(adjaux[x][i],auxv,adjaux);
}
auxv.push_back(x);
}
int main()
{
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m;
cin>>n>>m;
adj.resize(n+1,{});
adj_rev.resize(n+1,{});
for(int i = 0; i < m; i++)
{
int a,b;
cin>>a>>b;
adj[a].push_back(b);
}
vector<int>ordine;
for(int i = 1; i <= n; i++)
{
if(!visited[i])
{
dfs(i,ordine,adj);
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 0; j < adj[i].size(); j++)
{
adj_rev[adj[i][j]].push_back(i);
}
visited[i] = 0;
}
for(int i = ordine.size()-1; i >= 0; i--)
{
if(!visited[ordine[i]])
{
vector<int>componenta;
dfs(ordine[i],componenta,adj_rev);
sort(componenta.begin(),componenta.end());
ans.push_back(componenta);
}
}
cout<<(int)(ans.size())<<'\n';
for(int i = 0; i < ans.size(); i++)
{
for(int j = 0; j < ans[i].size(); j++)
{
cout<<ans[i][j]<<" ";
}
cout<<'\n';
}
return 0;
}