Pagini recente » Cod sursa (job #46974) | Cod sursa (job #2392561) | Cod sursa (job #740518) | Arhiva de probleme | Cod sursa (job #934632)
Cod sursa(job #934632)
#include <fstream>
#include <vector>
#define MAX 100005
using namespace std;
int N, M, k, viz[MAX], ctc[MAX];
vector<int> Gi[MAX], Go[MAX], discovered, V[MAX];
void citire() {
ifstream in("ctc.in");
in>>N>>M;
for(int i = 1, A, B; i <= M; i++) {
in>>A>>B;
Go[A].push_back(B);
Gi[B].push_back(A);
} in.close();
}
void DFF(int nod) {
viz[nod] = true;
for(size_t i = 0; i < Go[nod].size(); i++) {
int dest = Go[nod][i];
if(!viz[dest]) DFF(dest);
} discovered.push_back(nod);
}
void DFS(int nod, int ind) {
ctc[nod] = ind;
for(size_t i =0 ; i < Gi[nod].size(); i++) {
int dest = Gi[nod][i];
if(!ctc[dest]) DFS(dest, ind);
}
}
void solve() {
for(int i = 1; i <= N; i++)
if(!viz[i]) DFF(i);
for(; discovered.size(); discovered.pop_back()) {
int nod = discovered.back();
if(!ctc[nod]) DFS(nod, ++k);
}
for(int i = 1; i <= N; i++)
V[ctc[i]].push_back(i);
}
void afisare() {
ofstream out("ctc.out");
out<<k<<"\n";
for(int i = 1; i <= k; i++) {
for(size_t j = 0; j < V[i].size(); j++) out<<V[i][j]<<" ";
out<<"\n";
} out.close();
}
int main() {
citire();
solve();
afisare();
return 0;
}