Pagini recente » Cod sursa (job #1159407) | Cod sursa (job #1621561) | Istoria paginii utilizator/commercialgas686 | Cod sursa (job #942081) | Cod sursa (job #1896042)
#include <fstream>
#include <vector>
#define NMAX 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[NMAX];
vector <int> GT[NMAX];
vector <int> CTC[NMAX];
int nr, n, m, postordine[NMAX], poz;
bool uz[NMAX];
void citire();
void DFS(int k);
void DFST(int k);
void afisare();
int main() {
int i;
citire();
for (i=1; i<=n; i++)
if (!uz[i])
DFS(i);
for (i=n; i>=1; i--)
if (uz[postordine[i]]) {
nr++;
DFST(postordine[i]);
}
afisare();
fin.close();
fout.close();
return 0;
}
void afisare() {
int i;
int j;
int lg;
fout<<nr<<'\n';
for (i=1; i<=nr; i++) {
lg=CTC[i].size();
for (j=0; j<lg; j++)
fout<<CTC[i][j]<<' ';
fout<<'\n';
}
}
void DFST(int k) {
int i;
int lg=GT[k].size();
uz[k]=0;
CTC[nr].push_back(k);
for (i=0; i<lg; i++)
if (uz[GT[k][i]])
DFST(GT[k][i]);
}
void DFS(int k) {
int i;
int lg=G[k].size();
uz[k]=1;
//parcurg lista de adiacenta al lui x
for (i=0; i<lg; i++)
if (!uz[G[k][i]])
DFS(G[k][i]);
postordine[++poz]=k;
}
void citire() {
int i;
int x, y;
fin>>n>>m;
for (i=1; i<=m; i++) {
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
}