Pagini recente » Cod sursa (job #813985) | Cod sursa (job #557526) | Cod sursa (job #926974) | Cod sursa (job #2595667) | Cod sursa (job #2072296)
#include <cstdio>
using namespace std;
FILE *f, *g;
struct nod
{
int nr;
nod *urm;
};
nod *p, *lista[100009];
nod *compCTC[100009];
int d[100002];
int stk[1000002], stkLen;
int index[100002];
int depth;
bool onStack[100009];
void add(int a, int b)
{
p = new nod;
p -> urm = lista[a];
p -> nr = b;
lista[a] = p;
}
int n, m;
int CTC = 0;
inline int mna(int a, int b)
{
return (a < b ? a : b);
}
inline int mxa(int a, int b)
{
return (a > b ? a : b);
}
void readFile()
{
f = fopen("ctc.in", "r");
fscanf(f, "%d%d", &n, &m);
int i;
int a, b;
for(i = 1; i <= m; i ++)
{
fscanf(f, "%d%d", &a, &b);
add(a, b);
}
fclose(f);
}
int DFS(int nodul)
{
d[nodul] = index[nodul] = depth;
stk[++ stkLen] = nodul;
onStack[nodul] = true;
depth ++;
nod *p = lista[nodul];
///Pentru fiecare vecin
while(p != 0)
{
///Daca e muchie "arbore"
if(index[p -> nr] == -1)
{
DFS(p -> nr);
d[nodul] = mna(d[nodul], d[p -> nr]);
}
///Daca e muchie "inapoi"
else
if(onStack[p -> nr] == true)
{
d[nodul] = mna(d[nodul], index[p -> nr]);
}
///Altfel e muchie ianinte sau cross
///Mergem la urmatorul vecin
p = p -> urm;
}
///Nodul este radacina unei CTC
if(d[nodul] == index[nodul])
{
///Eticheteaza si scoate CTC de pe stiva
CTC ++;
int nodVecin;
do
{
nodVecin = stk[stkLen --];
onStack[nodVecin] = false;
///Adauga la CTCa curenta
p = new nod;
p -> nr = nodVecin;
p -> urm = compCTC[CTC];
compCTC[CTC] = p;
}
while(nodVecin != nodul);
}
return d[nodul];
}
void tarzjan()
{
int i;
for(i = 1; i <= n; i ++)
{
///Pentru fiecare nod nevizitat
if(index[i] == -1)
DFS(i);
}
}
void init0()
{
int i;
for(i = 1; i <= n; i ++)
index[i] = -1;
}
void solve()
{
init0();
tarzjan();
}
void printFile()
{
g = fopen("ctc.out", "w");
fprintf(g, "%d\n", CTC);
int i;
for(i = 1; i <= CTC; i ++)
{
p = compCTC[i];
while(p != 0)
{
fprintf(g, "%d ", p -> nr);
p = p -> urm;
}
fprintf(g, "\n");
}
fclose(g);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}