Pagini recente » Cod sursa (job #104116) | Cod sursa (job #2506120) | Cod sursa (job #172163) | Cod sursa (job #1915962) | Cod sursa (job #862711)
Cod sursa(job #862711)
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin ("ctc.in"); ofstream fout ("ctc.out");
short int *mat[25001];
short int n, m, i, a, b, ct, cc, post[25001], j;
bool viz[25001];
short int *trans[25001];
short int *comp[25001];
void dfs (short int s) {
short int i;
viz[s]=1;
for (i=1; i<=mat[s][0]; ++i) if (!viz[mat[s][i]]) dfs(mat[s][i]);
post[++ct]=s;
}
void dfst (short int s) {
short int i;
comp[cc]=(short int*)realloc(comp[cc], (++comp[cc][0]+1)*sizeof(short int));
comp[cc][comp[cc][0]]=s;
viz[s]=0; for (i=1; i<=trans[s][0]; ++i) if (viz[trans[s][i]]) dfst(trans[s][i]);
}
int main()
{
//algoritm folosit pentru determinarea componentelor tare-conexe
//parcurge graful DFS si retine ordinea varfurilor parcurse in postordine
//se parcurge apoi graful transpus dupa lista postordonata a varfurilor,
//in ordine INVERSA, componentele identificate fiind de natura tare conexa
fin>>n>>m;
for (i=1; i<=n; ++i) {
mat[i]=(short int*)realloc(mat[i], sizeof(short int)); mat[i][0]=0;
trans[i]=(short int*)realloc(trans[i], sizeof(short int)); trans[i][0]=0;
comp[i]=(short int*)realloc(comp[i], sizeof(short int)); comp[i][0]=0;
}
for (i=1; i<=m; ++i) {
fin>>a>>b;
mat[a]=(short int*)realloc(mat[a], (++mat[a][0]+1)*sizeof(short int)); mat[a][mat[a][0]]=b;
trans[b]=(short int*)realloc(trans[b], (++trans[b][0]+1)*sizeof(short int)); trans[b][trans[b][0]]=a;
}
for (i=1; i<=n; ++i) if (!viz[i]) dfs(i);
for (i=n; i>=1; --i) if (viz[post[i]]) {
++cc;
dfst(post[i]);
}
fout<<cc<<'\n'; for (i=1; i<=cc; ++i) { for (j=1; j<=comp[i][0]; ++j) fout<<comp[i][j]<<' '; fout<<'\n'; }
fout.close();
return 0;
}