Pagini recente » Cod sursa (job #3229692) | Cod sursa (job #837634) | Cod sursa (job #2757133) | Cod sursa (job #1417951) | Cod sursa (job #862719)
Cod sursa(job #862719)
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin ("ctc.in"); ofstream fout ("ctc.out");
int *mat[100001];
int n, m, i, a, b, ct, cc, post[100001], j;
bool viz[100001];
short int *trans[100001];
int *comp[100001];
void dfs (int s) {
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 (int s) {
int i;
comp[cc]=(int*)realloc(comp[cc], (++comp[cc][0]+1)*sizeof(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]=(int*)realloc(mat[i], sizeof(int)); mat[i][0]=0;
trans[i]=(int*)realloc(trans[i], sizeof(int)); trans[i][0]=0;
comp[i]=(int*)realloc(comp[i], sizeof(int)); comp[i][0]=0;
}
for (i=1; i<=m; ++i) {
fin>>a>>b;
mat[a]=(int*)realloc(mat[a], (++mat[a][0]+1)*sizeof(int)); mat[a][mat[a][0]]=b;
trans[b]=(int*)realloc(trans[b], (++trans[b][0]+1)*sizeof(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;
}