Pagini recente » Cod sursa (job #3181037) | Cod sursa (job #2179922) | Cod sursa (job #231163) | Cod sursa (job #2507720) | Cod sursa (job #1895208)
#include <fstream>
#include <vector>
#define Ndim 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int index,nrctc,Q[Ndim];
bool VIZ[Ndim];
struct vertex{int index,lowlink;bool inQ;}V[Ndim];
vector <int> G[Ndim],CTC[Ndim];
void StrongConnect(int nod)
{
VIZ[nod] = 1;
V[nod].index = index;
V[nod].lowlink = index;
index++;
Q[++Q[0]] = nod;
V[nod].inQ = true;
for(size_t i=0;i<G[nod].size();i++)
{
int fiu = G[nod][i];
if(VIZ[fiu]==0)
{
StrongConnect(fiu);
V[nod].lowlink = min(V[nod].lowlink, V[fiu].lowlink);
}
else if(V[fiu].inQ == true)
{
V[nod].lowlink = min(V[nod].lowlink, V[fiu].lowlink);
}
}
int x;
if(V[nod].index == V[nod].lowlink)
{
nrctc++;
do
{
x = Q[Q[0]];
Q[0]--;
CTC[nrctc].push_back(x);
V[x].inQ = false;
}while(x!=nod);
}
}
int main()
{
int n,m,i,a,b,j;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>a>>b;
G[a].push_back(b);
}
for(i=1;i<=n;i++)
{
if(VIZ[i]==0)
{
StrongConnect(i);
}
}
fout<<nrctc<<'\n';
for(i=1;i<=nrctc;i++,fout<<'\n')
{
for(j=0;j<CTC[i].size();j++)
fout<<CTC[i][j]<<' ';
}
return 0;
}