Pagini recente » preoni-2007/runda-finala/poze/evaluare | Cod sursa (job #344919) | Cod sursa (job #2255780) | Cod sursa (job #2668948) | Cod sursa (job #1038354)
#include<cstdio>
#include<vector>
using namespace std;
FILE* fout;
int nrNoduri;
vector<int> listeAdiacenta[100008];
vector<int> listeTranspuse[100008];
int postOrdine[100008];
int indPostOrdine = 0;
bool used[100008];
vector<int> componente[100008];
int nrComponente;
void init();
void citire();
void genPostOrdine();
void genComponente();
void afisare();
int main(){
citire();
genPostOrdine();
genComponente();
afisare();
return 0;
}
void citire(){
FILE* fin = fopen("ctc.in", "r");
int nrMuchii;
int nod1, nod2;
//fin >> nrNoduri >> nrMuchii;
fscanf(fin, "%d%d", &nrNoduri, &nrMuchii);
while(nrMuchii){
//fin >> nod1 >> nod2;
fscanf(fin, "%d\%d", &nod1, &nod2);
listeAdiacenta[nod1 - 1].push_back(nod2 - 1);
listeTranspuse[nod2 - 1].push_back(nod1 - 1);
nrMuchii--;
}
fclose(fin);
}
void dfsPostOrdine(int nod);
void genPostOrdine(){
int i;
for (i = 0; i < nrNoduri; i++){
if (!used[i]){
dfsPostOrdine(i);
}
}
}
void dfsPostOrdine(int nod){
int i;
used[nod] = 1;
for (i = 0; i < listeAdiacenta[nod].size(); i++){
if (!used[listeAdiacenta[nod][i]]){
dfsPostOrdine(listeAdiacenta[nod][i]);
}
}
postOrdine[indPostOrdine++] = nod;
}
void dfsTranspus(int nod);
void genComponente(){
int i;
for (i = 0; i < nrNoduri; i++){
used[i] = 0;
}
for (i = nrNoduri - 1; i >= 0; i--){
if (!used[postOrdine[i]]){
nrComponente++;
dfsTranspus(postOrdine[i]);
}
}
}
void dfsTranspus(int nod){
componente[nrComponente].push_back(nod);
used[nod] = 1;
int i;
for (i = 0; i < listeTranspuse[nod].size(); i++){
if (!used[listeTranspuse[nod][i]]){
dfsTranspus(listeTranspuse[nod][i]);
}
}
}
void afisare(){
int i, j;
fout = fopen("ctc.out", "w");
fprintf(fout, "%d\n", nrComponente);
for (i = 1; i <= nrComponente; i++){
fprintf(fout, "%d", componente[i][0]);
for (j = 1; j < componente[i].size(); j++){
fprintf(fout, " %d", componente[i][j]);
}
fprintf(fout, "\n");
}
fclose(fout);
}