Pagini recente » Cod sursa (job #166132) | Cod sursa (job #1177118) | Cod sursa (job #1395616) | Cod sursa (job #1779388) | Cod sursa (job #2084309)
#include <iostream>
#include <fstream>
#include <stack>
#include <list>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack <int> s;
list <int> :: iterator it,sf;
int n,m,T,index[32000],low[32001];
list <int> lista[32001];
bool st[32001];
void sc(int v);
void tarjan()
{
for(int i=1;i<=n;i++)
if(!index[i])
sc(i);
}
int k=1;
int nr;
void sc(int v)
{
index[v]=k;
low[v]=k;
k++;
s.push(v);
st[v]=true;
sf=lista[v].end();
it=lista[v].begin();
while(it!=sf)
{
int w=*it;
if(!index[w])
{
sc(w);
low[v]=min(low[v],low[w]);
}
else if(st[w])
low[v]=min(low[v],index[w]);
++it;
}
if(low[v]==index[v])
{
int w;
do
{
w=s.top();
s.pop();
st[w]=0;
index[w]=index[v];
}
while(w!=v);
}
}
int main()
{
f>>n>>m;
int i,j;
while(m--)
{f>>i>>j;
lista[i].push_back(j);}
tarjan();
for(int i=1;i<=n;i++)
if(index[i]>0)
{
nr++;
for(int j=i+1;j<=n;j++)
if(index[i]==index[j])
index[j]=(-1)*index[i];
index[i]=(-1)*index[i];
}
g<<nr<<endl;
for(int i=1;i<=n;i++)
if(index[i]<0)
{g<<i<<' ';
for(int j=i+1;j<=n;j++)
if(index[i]==index[j])
{g<<j<<' ';
index[j]=0;
}
index[i]=0;
g<<endl;
}
return 0;
}