Pagini recente » Cod sursa (job #639654) | Cod sursa (job #153726) | Cod sursa (job #1807197) | Cod sursa (job #1920059) | Cod sursa (job #1460669)
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <list>
#include <vector>
using namespace std;
class graph {
private:
vector< list<int> > adiac;
public:
graph(int n) {
adiac.resize(n);
}
int size() {
return adiac.size();
}
const list<int>& neigh(int nod) {
return adiac[nod];
}
void insertEdge(int n1, int n2) {
adiac[n1].push_back(n2);
}
void simpleDFS(int nod, vector<char> &visited, vector<int> &finished) {
visited[nod] = 1;
auto L = this->neigh(nod);
for (auto i = L.begin(); i != L.end(); ++i)
if (!visited[*i])
this->simpleDFS(*i, visited, finished);
finished.push_back(nod);
}
void getCompDFS(int nod, vector<char> &visited, vector<int> &ordered) {
visited[nod] = 1;
ordered.push_back(nod);
auto L = this->neigh(nod);
for (auto i = L.begin(); i != L.end(); ++i)
if (!visited[*i])
this->simpleDFS(*i, visited, ordered);
}
};
int main() {
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int N, M;
scanf("%d %d", &N, &M);
graph* G = new graph(N);
graph* revG = new graph(N);
for (int i = 0; i < M; i++) {
int a, b;
scanf("%d %d", &a, &b);
G->insertEdge(a - 1, b - 1);
revG->insertEdge(b - 1, a - 1);
}
vector<int> finished; finished.reserve(N);
vector<char> visited(N, 0);
for (int i = 0; i < N; i++)
if (!visited[i])
revG->simpleDFS(i, visited, finished);
delete revG;
visited.assign(N, 0);
int nrComp = 0;
vector<int> orderedNodes; orderedNodes.reserve((N << 1) + 2);
for (auto i = finished.rbegin(); i != finished.rend(); ++i)
if (!visited[*i]) {
nrComp++;
G->getCompDFS(*i, visited, orderedNodes);
orderedNodes.push_back(-1);
}
printf("%d\n", nrComp);
for (auto i = orderedNodes.begin(); i != orderedNodes.end(); ++i) {
if (*i == -1)
printf("\n");
else
printf("%d ", (*i) + 1);
}
return 0;
}