Pagini recente » Cod sursa (job #1995416) | Cod sursa (job #2702802) | Cod sursa (job #3244669) | Cod sursa (job #2554033) | Cod sursa (job #2810205)
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
struct ct
{
int nr,va;
};
ct v[100002];
vector<vector<int> >mu1,mu2;
stack<int>st;
int f[100002],x,y,n,m;
void DFS1(int x)
{
f[x]=1;
for(int j=0;j<mu1[x].size();j++)
if(f[mu1[x][j]]==0)
DFS1(mu1[x][j]);
st.push(x);
}
void DFS2(int x,int val)
{
v[x].va=val;
for(int j=0;j<mu2[x].size();j++)
if(v[mu2[x][j]].va==0)
DFS2(mu2[x][j],val);
}
bool sorta(ct a,ct b)
{
if(a.va>b.va)
return 0;
if(a.va==b.va && a.nr>b.nr)
return 0;
return 1;
}
int main()
{
cin>>n>>m;
mu1.resize(n+1);
mu2.resize(n+1);
for(int i=1;i<=m;i++)
{
cin>>x>>y;
mu1[x].push_back(y);
mu2[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
v[i].nr=i;
if(f[i]==0)
DFS1(i);
}
int cnt=1;
while(st.empty()==0)
{
int q=st.top();
if(v[q].va==0)
DFS2(q,cnt),cnt++;
st.pop();
}
cout<<cnt<<'\n';
sort(v+1,v+n+1,sorta);
cnt=1;
for(int i=1;i<=n;i++)
{
if(v[i].va>cnt)
{
cout<<'\n';
cnt++;
}
if(v[i].va==cnt)
cout<<v[i].nr<<' ';
}
}