Pagini recente » Cod sursa (job #570182) | Borderou de evaluare (job #1093670) | Cod sursa (job #1110399) | Cod sursa (job #1911694) | Cod sursa (job #354398)
Cod sursa(job #354398)
#include<iostream>
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define nMax 100010
int n,m,nrSol;
vector <int> a[nMax];
vector <int> gt[nMax];
vector <int> ut(nMax,0);
vector <int> rez[nMax];
vector <int> noD(1);
void solve(int N)
{
stack <int> st;
st.push(N);
vector <int> utFirst(ut);
utFirst[N]=1;
vector <int> ut1(n+1,0);
while(!st.empty())
{
int nod=st.top();
st.pop();
ut1[nod]=1;
for(vector <int> ::iterator it=a[nod].begin();it!=a[nod].end();it++)
{
if(utFirst[*it])
continue;
st.push(*it);
utFirst[*it]=1;
}
}
st.push(N);
vector <int> utSecond(ut);
utSecond[N]=1;
vector <int> ut2(n+1,0);
while(!st.empty())
{
int nod=st.top();
st.pop();
ut2[nod]=1;
for(vector <int> ::iterator it=gt[nod].begin();it!=gt[nod].end();it++)
{
if(utSecond[*it])
continue;
st.push(*it);
utSecond[*it]=1;
}
}
nrSol++;
for(int i=1;i<=n;i++)
if(ut1[i]&&ut2[i])
{
ut[i]=1;
rez[nrSol].push_back(i);
}
if(rez[nrSol].empty())
nrSol--;
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
gt[y].push_back(x);
}
for(int i=1;i<=n;i++)
noD.push_back(i);
random_shuffle(noD.begin()+1,noD.end());
for(int i=1;i<=n;i++)
if(!ut[noD[i]])
solve(noD[i]);
printf("%d\n",nrSol);
for(int i=1;i<=nrSol;i++)
{
for(vector <int> ::iterator it=rez[i].begin();it!=rez[i].end();it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}