Pagini recente » Cod sursa (job #1177804) | Cod sursa (job #2642124) | Cod sursa (job #632646) | Cod sursa (job #898924) | Cod sursa (job #2870633)
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
struct graf
{
int val,ind;
};
graf v[100002];
vector<vector<int> >mu1,mu2;
stack<int>st;
int n,m,x,y,f[100002];
void DFS1(int nod)
{
f[nod]=1;
for(int i=0; i<mu1[nod].size(); i++)
if(f[mu1[nod][i]]==0)
DFS1(mu1[nod][i]);
st.push(nod);
}
void DFS2(int nod,int val)
{
v[nod].val=val;
for(int i=0; i<mu2[nod].size(); i++)
if(v[mu2[nod][i]].val==0)
DFS2(mu2[nod][i],val);
}
bool sorta(graf a,graf b)
{
if(a.val>b.val)
return 0;
if(a.val==b.val && a.ind>b.ind)
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++)
{
if(f[i]==0)
DFS1(i);
v[i].ind=i;
}
int cnt=1;
while(st.empty()==0)
{
int q=st.top();
st.pop();
if(v[q].val==0)
{
DFS2(q,cnt);
cnt++;
}
}
sort(v+1,v+n+1,sorta);
cout<<cnt-1<<'\n';
cnt=1;
for(int i=1; i<=n; i++)
{
if(v[i].val==cnt)
cout<<v[i].ind<<' ';
else
{
cout<<'\n';
cnt++;
cout<<v[i].ind<<' ';
}
}
}