Pagini recente » Cod sursa (job #2582917) | Cod sursa (job #622457) | Cod sursa (job #2252846) | Cod sursa (job #2429625) | Cod sursa (job #1824658)
#include <fstream>
#include <stdint.h>
using namespace std;
fstream f1("ctc.in", ios::in);
fstream f2("ctc.out", ios::out);
///componenete tari-conexe, algoritmul lui kosaraju
///idee: iti faci un vector nrc[<n>] care tine minte din a cata comp conexa face parte nodul i
///pentru fiecare nod i, cu nrc[i]=0, identifici cu 2 parcurgeri bfs recursive succesorii si predecesorii nodului
///nr se reactualizeaza la fiecare rulare a for-ului si reprezinta nr de componente conexe init 0
///s[x]=nr daca nodul x este succesor pt i
///p[x]=nr daca nodul y este predecesor pentru i
///s[i]=nr, p[i]=nr implicit
///daca nodul x este si succ si predecesor, atunci x face parte din aceeasi componenta conexa ca si nodul i
///deoarece poti ajunge pe un drum de la x la i, dar si de la i la x
///pui in nrc[i] si nrcc[x], cu propr ca s[x]=nr si p[x]=nr, val nr
///pt p[x]==0 sau s[x]==0 pui p[x]=s[x]=0///nodul x nu face parte din nicio comp conexa
int32_t n, m, s[100001], p[100001], nrc[100001], v1[200001],v2[200001], nr, cap1[100001],cap2[100001];
struct muchie
{
int32_t x, y;
}muc[200001];
///v1 este o lista de adiacenta care tine minte vecini x->y, y este vecin al lui x, dar nu si invers
///v1 are dim nr de muchii
///cap1[i] tine minte indicii de unde incep vecinii nodului i
///v2 este lista de adiacenta a grafului transpus y->x
void bfss(int32_t i)
{
int32_t j;
for(j=cap1[i]; j<cap1[i+1]; j++)
if(!s[v1[j]])
{
s[v1[j]]=nr;
bfss(v1[j]);
}
}
void bfsp(int32_t i)
{
int32_t j;
for(j=cap2[i]; j<cap2[i+1]; j++)
if(!p[v2[j]])
{
///v2[j] este tata pentru i
p[v2[j]]=nr;
bfsp(v2[j]);
}
}
int main()
{
int32_t i, x, y, j;
f1>>n>>m;
for(i=1; i<=m; i++)
{
f1>>x>>y;
///s[i] devine in final nr succ nodul i
///in muc tii minte muchiile provizoriu
///p[i] devine in final nr pred
s[x]++;
p[y]++;
muc[i].x=x;
muc[i].y=y;
}
///construiesti vect cap1 si cap2
cap1[1]=1;
cap2[1]=1;
for(i=1; i<=n; i++)///ca sa stii si cap[n+1]
{
cap1[i+1]=cap1[i]+s[i];
s[i]=cap1[i];
cap2[i+1]=cap2[i]+p[i];
p[i]=cap2[i];
}
///construiesti lista de adiacenta
for(i=1; i<=m; i++)
{
x=muc[i].x;
y=muc[i].y;
v1[s[x]]=y;
s[x]++;
///x este predecesor al lui y, x->y
v2[p[y]]=x;
p[y]++;
}
for(i=1; i<=n; i++) {s[i]=0;p[i]=0;}
///pentru fiecare nod care nu se afla intr o comp conexa
for(i=1; i<=n; i++)
if(!nrc[i])
{
nr++;
nrc[i]=nr;
s[i]=nr;
p[i]=nr;
///afli predecesorii si succesorii nodului i
bfss(i);
bfsp(i);
///nodul j face parte din componenta conexa nr sau nu
for(j=1; j<=n; j++)
if((p[j]==nr)&&(s[j]==nr)) nrc[j]=nr;
else if((p[j]==0)||(s[j]==0)) {p[j]=s[j]=0;}
}
f2<<nr<<"\n";
///afisezi pe cate o linie nodurile din fiecare comp conexa
for(i=1; i<=nr; i++)
{
for(j=1; j<=n; j++)
if(nrc[j]==i) f2<<j<<" ";
f2<<"\n";
}
return 0;
}