Pagini recente » Borderou de evaluare (job #1099101) | Borderou de evaluare (job #204889) | Cod sursa (job #2916007) | Borderou de evaluare (job #463198) | Cod sursa (job #2651411)
#include <fstream>
using namespace std;
const int NMAX = 100000;
struct nod
{
int x;
nod *next;
};
nod *G[NMAX + 1], ///lista vecinilor, graf initial
*GT[NMAX + 1], ///lista vecinilor, graf transpus
*CTC[NMAX + 1]; ///lista nodurilor componentei tare conexe
int n,m,nrc,
nr,post[NMAX + 1];
bool viz[NMAX + 1];
ifstream f("ctc.in");
ofstream g("ctc.out");
void add(nod *&cap_1st,int nod_ad)
{
nod *p;
p = new nod;
p -> x = nod_ad;
p -> next = cap_1st;
cap_1st = p;
}
void citireGraf()
{
int x,y;
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>x>>y;
add(G[x],y);///adaug arc in G
add(GT[y],x);///adaug arc in GT
}
}
void DFS(int vf)///Determinam toate nodurile in care se poate ajunge din vf
{
viz[vf] = 1; ///+
for(nod *p = G[vf]; p != NULL; p = p -> next)
if(viz[p->x] == 0)
DFS(p->x);
post[++nr] = vf;///se memoreaza ordinea de parcurgere a nodurilor(postordine)
}
void componente() ///Algoritmul Kosaraju-Sharir
{
for(int i=1;i<=n;i++)
if(viz[i] == 0)
DFS(i); ///DFS pe graful initial
//
for(int i=n;i>=1;i--) ///se parcurg nodurile in postordine
if(viz[post[i]] == 1) ///nodul post[i] nu a fost plasat intr-o CTC
{
nrc++;
DFS(post[i]); ///DFS pe graful transpus
}
}
void afis()
{
g<<nrc<<'\n';
for(int i=1;i<=nrc;i++)
{
for(nod *p = CTC[i]; p!=NULL; p = p -> next)
g<< p->x <<' ';
g<<'\n';
}
}
int main()
{
citireGraf();
componente();
afis();
return 0;
}