Pagini recente » Cod sursa (job #2058069) | Cod sursa (job #1904946) | Cod sursa (job #2969147) | Cod sursa (job #687535) | Cod sursa (job #1283238)
#include <fstream>
#include <stack>
#include <list>
#define DIM 200001
using namespace std;
int minim(int a, int b)
{
if(a<b) return a;
else return b;
}
ifstream in ("ctc.in");
ofstream out("ctc.out");
int idx[DIM], lowlink[DIM], a, b, tconex[DIM], v[DIM];
int n, m, index, varf, vf, x, nrcon;
stack <int> st;
list <int> nod[DIM];
void tarjan(int vf)
{
idx[vf]=(++index);
lowlink[vf]=index;
st.push(vf);
for(list <int>::iterator j=nod[vf].begin(); j!=nod[vf].end(); ++j)
{
if(idx[*j]>0)
lowlink[vf]=minim(lowlink[vf], lowlink[*j]);
else if (idx[*j]==0)
{
tarjan(*j);
lowlink[vf]=minim(lowlink[vf], lowlink[*j]);
}
}
if(lowlink[vf]==idx[vf])
{
nrcon++;
do
{
varf=st.top();
st.pop();
tconex[++x]=varf;
idx[varf]=-1;
}while(varf!=vf);
v[nrcon]=vf;
}
}
int main()
{
in>>n>>m;
while(m--)
{
in>>a>>b;
nod[a].push_back(b);
}
index=0;
for(int i=1; i<=n; ++i)
{
if(idx[i]==0)
tarjan(i);
}
out<<nrcon<<"\n";
nrcon=1;
for(int i=1; i<=n; ++i)
{
out<<tconex[i]<<" ";
if(v[nrcon]==tconex[i])
{
out<<"\n";
nrcon++;
}
}
in.close();
out.close();
return 0;
}