Pagini recente » Cod sursa (job #3250521) | Cod sursa (job #86406) | Cod sursa (job #2539019) | Cod sursa (job #407171) | Cod sursa (job #1831855)
#include <bits/stdc++.h>
using namespace std;
class Graph {
private:
int nodes;
vector <vector<int>> graph;
vector <vector<int>> SCC;
vector <int> idx, lowlink;
stack <int> stiva;
vector<bool> inStack;
int index;
int nrSCC;
void Tarjan(int node) {
if (idx[node] != 0)
return;
vector <int> :: iterator it;
idx[node] = lowlink[node] = index++;
stiva.push(node);
inStack[node] = 1;
for (auto it : graph[node]) {
if (!idx[it]) {
Tarjan(it);
lowlink[node] = min(lowlink[node], lowlink[it]);
}
else {
if (inStack[it])
lowlink[node] = min(lowlink[node], idx[it]);
}
}
if (lowlink[node] == idx[node]) {
int k;
nrSCC++;
do {
k = stiva.top();
stiva.pop();
inStack[k] = 0;
SCC[nrSCC].push_back(k);
}while (k != node);
}
}
public:
Graph(int nodes) {
this->nodes = nodes;
this->inStack.resize(nodes + 1);
this->graph.resize(nodes + 1);
this->idx.resize(nodes + 1);
this->lowlink.resize(nodes + 1);
this->index = 0;
this->nrSCC = 0;
}
void addEdge(const int x, const int y) {
this->graph[x].push_back(y);
}
vector<vector<int>> getSCC() {
SCC.resize(nodes + 1);
for (int i = 1; i <= nodes; ++i)
if (!idx[i])
Tarjan(i);
for (int i = 0; !nrSCC && i < nrSCC; ++i)
for (auto it : SCC[i])
SCC[i].push_back(it);
return SCC;
}
int countSCC() {
if (!nrSCC)
getSCC();
return this->nrSCC;
}
};
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int main() {
int N, M;
fin >> N >> M;
Graph myGraph(N);
while (M--) {
int x, y;
fin >> x >> y;
myGraph.addEdge(x, y);
}
vector<vector<int>> CTC(N + 1);
CTC = myGraph.getSCC();
fout << myGraph.countSCC() << "\n";
for (int i = 1; i <= myGraph.countSCC(); ++i) {
for (auto it : CTC[i])
fout << it << " ";
fout << "\n";
}
return 0;
}