Pagini recente » Cod sursa (job #1413464) | Cod sursa (job #1433507) | Cod sursa (job #2347448) | Cod sursa (job #722617) | Cod sursa (job #1291055)
#include <iostream>
#include <list>
#include <stack>
#include <fstream>
#include <vector>
#define NIL -1
using namespace std;
class Graph {
int V;
list<int> *adj;
void SCCUtil(int u, int disc[], int low[], stack<int> *st, bool stackMember[]);
public:
Graph(int V);
void addEdge(int v, int w);
void SCC();
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w) {
adj[v].push_back(w);
}
vector< vector<int>* > output;
void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st, bool stackMember[]) {
static int time = 0;
disc[u] = low[u] = ++time;
st->push(u);
stackMember[u] = true;
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i) {
int v = *i;
if (disc[v] == -1) {
SCCUtil(v, disc, low, st, stackMember);
low[u] = min(low[u], low[v]);
} else if (stackMember[v] == true)
low[u] = min(low[u], disc[v]);
}
int w = 0;
if (low[u] == disc[u]) {
vector<int>* out = new vector<int>();
while (st->top() != u) {
w = (int) st->top();
out->push_back(w);
stackMember[w] = false;
st->pop();
}
w = (int) st->top();
out->push_back(w);
stackMember[w] = false;
st->pop();
output.push_back(out);
}
}
void Graph::SCC() {
int *disc = new int[V];
int *low = new int[V];
bool *stackMember = new bool[V];
stack<int> *st = new stack<int>();
for (int i = 0; i < V; i++) {
disc[i] = NIL;
low[i] = NIL;
stackMember[i] = false;
}
for (int i = 0; i < V; i++)
if (disc[i] == NIL)
SCCUtil(i, disc, low, st, stackMember);
}
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define cin fin
#define cout fout
int main() {
int n, m;
cin >> n >> m;
Graph g(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
g.addEdge(x - 1, y - 1);
}
g.SCC();
cout << output.size() << "\n";
for (int i = 0; i < output.size(); i++) {
for (int j = 0; j < output[i]->size(); j++) {
cout << (*output[i])[j] + 1 << " ";
}
cout << "\n";
}
return 0;
}