Pagini recente » Cod sursa (job #2806604) | Cod sursa (job #119052) | Cod sursa (job #3179652) | Cod sursa (job #2478666) | Cod sursa (job #1181562)
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdexcept>
#include <stack>
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) {
data[x].push_back(y);
data[y].push_back(x);
}
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();
};
void DirectedGraph::addEdge(const int& x, const int& y) {
data[x].push_back(y);
}
vector< vector<int> > DirectedGraph::getSCC() {
vector<vector<int> > components;
if (vertexNumber == 0)
return components;
vector<bool> inStack(vertexNumber, false);
vector<int> inTime(vertexNumber, -1),
lowlink(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++;
}
bool allDone = true;
for (auto& w : data[v]) {
if (inStack[w])
lowlink[v] = min(lowlink[v], lowlink[w]);
else
if (allDone && inTime[w] == -1) {
dfsStack.push(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;
}
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;
}