Pagini recente » Cod sursa (job #1347404) | Cod sursa (job #241613) | Cod sursa (job #1850100) | Cod sursa (job #1605710) | Cod sursa (job #857480)
Cod sursa(job #857480)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define DN 100005
#define pb push_back
#define un unsigned
using namespace std;
vector<int> list[DN],v,liste[DN];
stack<int> s;
bool viz[DN];
int index[DN],min_index[DN],sz=0;
void dfs(int nod)
{
s.push(nod);
viz[nod]=true;
index[nod]=++index[0];
min_index[nod]=index[nod];
for(un int i=0;i<list[nod].size();++i)
{
int next_nod=list[nod][i];
if(!index[next_nod])
{
dfs(next_nod);
min_index[nod]=min(min_index[nod],min_index[next_nod]);
}
else if(viz[next_nod])
min_index[nod]=min(min_index[nod],index[next_nod]);
}
if(min_index[nod]==index[nod])
{
++sz;
liste[sz].pb(nod);
while(s.size() && s.top()!=nod)
{
liste[sz].pb(s.top());
s.pop();
}
s.pop();
}
}
int main()
{
int n,m;
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(;m;--m)
{
int x,y;
f>>x>>y;
list[x].pb(y);
}
for(int i=1;i<=n;++i)
if(!viz[i])
dfs(i);
g<<sz<<"\n";
for(int i=1;i<=sz;++i)
{
for(un int j=0;j<liste[i].size();++j)
g<<liste[i][j]<<" ";
g<<"\n";
}
return 0;
}