Pagini recente » Cod sursa (job #1620919) | Cod sursa (job #2413637) | Cod sursa (job #3286997) | Cod sursa (job #2292095) | Cod sursa (job #1185150)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#define pb push_back
#define p push
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
int N, M;
struct nod
{
int index, lowlink;
vector <int> next;
};
int index=1;
nod v[100001];
bool st[100001];
stack <int> S;
int nr_tot=0;
vector <int> rasp[100001];
void s_c (int i)
{
v[i].index=index;
v[i].lowlink=index;
++index;
S.p(i);
st[i]=1;
for (vector <int>::iterator it=v[i].next.begin(); it!=v[i].next.end(); ++it)
{
if (v[*it].index==0)
{
s_c(*it);
v[i].lowlink=min(v[i].lowlink, v[*it].lowlink);
}
else
{
if (st[*it]==1)
v[i].lowlink=min(v[i].lowlink, v[*it].index);
}
}
if (v[i].lowlink == v[i].index)
{
while (S.top()!=i)
{
rasp[nr_tot].pb(S.top());
st[S.top()]=0;
S.pop();
}
rasp[nr_tot].pb(i);
st[S.top()]=0;
S.pop();
++nr_tot;
}
return;
}
int main()
{
in>>N>>M;
for (int i=1;i<=N;++i)
{
v[i].index=0;
}
for (int i=0;i<M;++i)
{
int x, y;
in>>x>>y;
v[x].next.pb(y);
}
for (int i=1;i<=N;++i)
{
if (v[i].index==0)
s_c(i);
}
out<<nr_tot<<'\n';
for (int i=0;i<nr_tot;++i)
{
for ( vector <int>::iterator it=rasp[i].begin();it!=rasp[i].end();++it)
out<<*it<<" ";
out<<'\n';
}
return 0;
}