Pagini recente » Cod sursa (job #141991) | Cod sursa (job #2909597) | Cod sursa (job #2943012) | Cod sursa (job #3236523) | Cod sursa (job #2540998)
//
// main.cpp
// kosaraju
//
// Created by Razvan Vranceanu on 07/02/2020.
// Copyright © 2020 Razvan Vranceanu. All rights reserved.
//
#include <fstream>
#define N 100002
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, q[N], poz, nr;
bool vizG[N];
int vizGT[N];
struct nod{
int x;
nod *leg;
} *L[N], *LGT[N];
void adauga(nod *&pp, int val)
{
nod *p = new nod;
p -> x = val;
p -> leg =pp;
pp=p;
}
void citire()
{
int x,y;
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>x>>y;
adauga(L[x], y);
}
}
void GfTr()
{
nod *p;
for(int i=1;i<=n;i++)
for(p=L[i]; p; p=p->leg)
adauga(LGT[p->x], i);
}
void DF(int i)
{
vizG[i]=1;
for(nod *p=L[i]; p; p=p->leg)
if(!vizG[p->x])
DF(p->x);
q[++poz]=i;
}
void DFGT(int i, int nr)
{
vizGT[i]=nr;
nod *p;
for(p=LGT[i];p;p=p->leg)
if(vizGT[p->x] == 0)
DFGT(p->x, nr);
}
int main()
{
citire();
GfTr();
for(int i=1;i<=n;i++)
if(!vizG[i])
DF(i);
int contor=0;
for(int i=poz; i>=1; i--)
if(!vizGT[q[i]])
{
contor++;
DFGT(q[i], contor);
}
g<<contor;
int k=0;
while(k<=contor)
{
for(int i=1;i<=n;i++)
if(vizGT[i] == k)
g<<i<<" ";
g<<'\n';
k++;
}
return 0;
}