Pagini recente » Cod sursa (job #1285374) | Cod sursa (job #2565881) | Cod sursa (job #1547860) | Cod sursa (job #577895) | Cod sursa (job #1982289)
#include <fstream>
#include <stdint.h>
#define nmax 100001
#define mmax 200001
using namespace std;
fstream f1("ctc.in", ios::in);
fstream f2("ctc.out", ios::out);
int32_t aux[nmax], cap[nmax], auxt[nmax], capt[nmax], nrcomp;
int32_t v[mmax], vt[mmax], lista[nmax], l;
int32_t n, m, viz[nmax], viz2[nmax];
struct muc
{
int32_t x, y;
}muc[mmax];
///creezi 2 liste de adiacenta: una a grafului normal si una a grafului transpus
///viz2[i]= nr comp conexe din care face parte nodul i
void citire()
{
int32_t i, x, y;
f1>>n>>m;
for(i=1; i<=m; i++)
{
f1>>x>>y;
aux[x]++;
auxt[y]++;
muc[i].x=x;
muc[i].y=y;
}
}
void lista_ad()
{
int32_t i, x, y;
cap[1]=1;
for(i=2; i<=n+1; i++)
{
cap[i]=cap[i-1]+ aux[i-1];
aux[i-1]=cap[i-1];
}
for(i=1; i<=m; i++)
{
x=muc[i].x;
y=muc[i].y;
v[aux[x]]=y;
aux[x]++;
}
}
void lista_ad_t()
{
int32_t i, x, y;
capt[1]=1;
for(i=2; i<=n+1; i++)
{
capt[i]=capt[i-1]+ auxt[i-1];
auxt[i-1]=capt[i-1];
}
for(i=1; i<=m; i++)
{
x=muc[i].x;
y=muc[i].y;
vt[auxt[y]]=x;
auxt[y]++;
}
}
void dfs(int32_t nod)
{
int32_t i;
viz[nod]=1;
for(i=cap[nod]; i<cap[nod+1]; i++)
if(!viz[v[i]])
{
dfs(v[i]);
}
l++;
lista[l]=nod;
}
void dfs_transpus(int32_t nod)
{
int32_t i;
viz2[nod]=nrcomp;
for(i=capt[nod]; i<capt[nod+1]; i++)
if(!viz2[vt[i]])
{
viz2[vt[i]]=nrcomp;
dfs_transpus(vt[i]);
}
}
void afisare()
{
int32_t i, j;
f2<<nrcomp<<"\n";
for(i=1; i<=nrcomp; i++)
{
for(j=1; j<=n; j++)
if(viz2[j]==i) f2<<j<<" ";
f2<<"\n";
}
}
int main()
{
int32_t i;
citire();
lista_ad();
lista_ad_t();
for(i=1; i<=n; i++)
if(!viz[i])
dfs(i);
for(i=n; i>=1; i--)
if(!viz2[lista[i]])
{
nrcomp++;
dfs_transpus(lista[i]);
}
afisare();
return 0;
}