Pagini recente » Cod sursa (job #1543219) | Cod sursa (job #679048) | **** | Cod sursa (job #393374) | Cod sursa (job #3282528)
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("lant2.in");
ofstream gout("lant2.out");
vector<int>g[100001],gt[100001];
vector<int>post;
bool *viz;
void dfs(int i)
{
viz[i]=1;
for(int j:g[i])if(!viz[j])dfs(j);
post.push_back(i);
}
void dfsT(int i,vector<int>&d)
{
d.push_back(i);
viz[i]=1;
for(int j:gt[i])if(!viz[j])dfsT(j,d);
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
gout.tie(0);
int n,m,i,j;
fin>>n>>m;
viz=new bool[n+1];
fill(viz+1,viz+n+1,0);
while(m--)
{
fin>>i>>j;
g[i].push_back(j);
gt[j].push_back(i);
}
vector<vector<int>>ans;
for(i=1; i<=n; ++i)if(!viz[i])dfs(i);
fill(viz+1,viz+n+1,0);
for(auto it=post.rbegin(); it!=post.rend(); ++it)if(!viz[*it])
{
ans.push_back(vector<int>(0));
dfsT(*it,ans.back());
}
sort(ans.begin(),ans.end(),[](const vector<int>&d1,const vector<int>&d2)->bool{return d1[0]<d2[0];});
gout<<ans.size()<<'\n';
for(auto p:ans)
{
sort(p.begin(),p.end());
for(auto o:p)gout<<o<<' ';
gout<<'\n';
}
return 0;
}