Pagini recente » Cod sursa (job #2081468) | Cod sursa (job #1481382) | Cod sursa (job #3152695) | Cod sursa (job #1734121) | Cod sursa (job #1022015)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#define DN 100005
#define pb push_back
#define top stiva[0]
using namespace std;
vector<int> list[DN],tmp;
vector< vector<int> > rez;
bitset<DN> viz,ap;
int stiva[DN],low[DN],p,niv[DN];
void dfs(int nod)
{
viz[nod]=true;
low[nod]=++p;
niv[nod]=p;
stiva[++top]=nod;
ap[ nod ] = true;
for(int i=0;i<list[nod].size();++i){
int next_nod=list[nod][i];
if(!viz[next_nod]){
dfs(next_nod);
low[nod]=min(low[nod],low[next_nod]);
}
else
if(ap[next_nod]==true)
low[nod]=min(low[nod],low[next_nod]);
}
if(low[nod]==niv[nod])
{
while(1)
{
ap[ stiva[top] ] = false;
int a=stiva[top];
tmp.pb(stiva[top]);
--top;
if(a==nod)
break;
}
rez.pb(tmp);
tmp.clear();
}
//cout<<"NOD:"<<nod<<" LOW :"<<low[nod]<<endl;
}
int main()
{
int n,m;
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(;m;--m)
{
int a,b;
f>>a>>b;
list[a].pb(b);
}
for(int i=1;i<=n;++i)
if(!viz[i]){
dfs(i);
// p=0;
}
g<<rez.size()<<"\n";
for(int i=0;i<rez.size();++i,g<<"\n")
for(int j=0;j<rez[i].size();++j)
g<<rez[i][j]<<" ";
return 0;
}