Pagini recente » Cod sursa (job #2187967) | Cod sursa (job #794039) | Cod sursa (job #1722546) | Cod sursa (job #67643) | Cod sursa (job #1181716)
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdexcept>
#include <stack>
#include <tuple>
using namespace std;
class Graph
{
protected:
int vertexNumber;
int edgeNumber;
vector< vector<int> > data;
virtual void readData(istream& in);
virtual void writeData(ostream& out);
public:
Graph(int vertexNumber_);
Graph(int vertexNumber_, int edgeNumber, const vector< pair<int, int> >& edges);
virtual ~Graph();
virtual void addEdge(const int&x, const int& y);
friend istream& operator >> (istream& in, Graph& graph);
friend ostream& operator << (ostream& out, Graph& graph);
};
Graph::Graph(int vertexNumber_ = 0) {
vertexNumber = vertexNumber_;
data.resize(vertexNumber);
}
Graph::Graph(int vertexNumber_, int edgeNumber_, const vector< pair<int, int> >& edges) {
vertexNumber = vertexNumber_;
edgeNumber = edgeNumber_;
data.resize(vertexNumber);
for (const auto& edge : edges) {
addEdge(edge.first, edge.second);
}
}
Graph::~Graph() {
vertexNumber = 0;
}
void Graph::addEdge(const int& x, const int& y) {
try {
if (x < 0 || x >= vertexNumber || y < 0 || y >= vertexNumber) {
out_of_range outException("Node index out of bounds!");
throw outException;
}
data[x].push_back(y);
data[y].push_back(x);
}
catch (out_of_range& exception) {
cout << exception.what() << "\n";
}
}
void Graph::readData(istream& in) {
in >> vertexNumber >> edgeNumber;
data.clear();
data.resize(vertexNumber);
int a, b;
for (int i = 0; i < edgeNumber; i++) {
in >> a >> b;
a--, b--;
addEdge(a, b);
}
}
void Graph::writeData(ostream& out) {
out << vertexNumber << " " << edgeNumber << "\n";
for (int v = 0; v < vertexNumber; v++) {
for (const int& w : data[v]) {
if (v < w) {
out << v << " " << w << "\n";
}
}
}
}
istream& operator >> (istream& in, Graph& graph) {
graph.readData(in);
return in;
}
ostream& operator << (ostream& out, Graph& graph) {
graph.writeData(out);
return out;
}
class DirectedGraph : public Graph
{
public:
virtual void addEdge(const int& x, const int& y);
vector< vector<int> > getSCC();
};
vector< vector<int> > DirectedGraph::getSCC() {
vector<vector<int> > components;
if (vertexNumber == 0)
return components;
vector<bool> inStack(vertexNumber, false);
vector< vector<int>::iterator > nextNode(vertexNumber);
vector<int> inTime(vertexNumber, -1),
lowlink(vertexNumber, -1),
who(vertexNumber, -1);
stack<int> dfsStack, S;
int indexCount = 0;
for (int i = 0; i < vertexNumber; i++) {
if (inTime[i] != -1) continue;
dfsStack.push(i);
while (!dfsStack.empty()) {
int v = dfsStack.top();
if (inTime[v] == -1) {
S.push(v);
inStack[v] = true;
inTime[v] = lowlink[v] = indexCount++;
nextNode[v] = begin(data[v]);
} else
if (who[v] != -1) {
auto& w = who[v];
if (inStack[w])
lowlink[v] = min(lowlink[v], lowlink[w]);
}
bool allDone = true;
while (allDone && nextNode[v] != end(data[v])) {
auto w = *(nextNode[v]++);
if (inStack[w])
lowlink[v] = min(lowlink[v], lowlink[w]);
else
if (allDone && inTime[w] == -1) {
dfsStack.push(w);
who[v] = w;
allDone = false;
}
}
if (allDone) {
if (inTime[v] == lowlink[v]) {
components.push_back(vector<int>());
int w;
do {
w = S.top();
inStack[w] = false;
components.back().push_back(w);
S.pop();
} while (w != v);
}
dfsStack.pop();
}
}
}
return components;
}
void DirectedGraph::addEdge(const int& x, const int& y) {
data[x].push_back(y);
}
int main() {
ifstream cin("ctc.in");
ofstream cout("ctc.out");
DirectedGraph G;
cin >> G;
vector< vector<int> > c = G.getSCC();
cout << c.size() << "\n";
for (auto& nodes : c) {
for (auto& x : nodes)
cout << x + 1 << " ";
cout << "\n";
}
return 0;
}