Pagini recente » Cod sursa (job #2579143) | Cod sursa (job #2398003) | Cod sursa (job #1317012) | Cod sursa (job #2822609) | Cod sursa (job #1399039)
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#define MAXV 100001
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int V, A;
vector <int> G[MAXV];
vector <vector <int>> scc;
int value[MAXV];
int lowlink[MAXV];
stack <int> st;
int currentValue = 1;
bool inStack[MAXV];
inline void readAndBuild() {
in >> V >> A;
int x, y;
for (int a = 0; a < A; ++ a) {
in >> x >> y;
G[x].push_back(y);
}
}
inline void dfs(int node) {
st.push(node);
inStack[node] = true;
value[node] = currentValue;
lowlink[node] = currentValue;
currentValue ++;
for (vector <int>::iterator it = G[node].begin(); it != G[node].end(); ++ it) {
if (value[*it] == 0) {
dfs(*it);
lowlink[node] = min(lowlink[node], lowlink[*it]);
} else if (inStack[*it]) {
lowlink[node] = min(lowlink[node], value[*it]);
}
}
if (value[node] == lowlink[node]) {
vector <int> newScc;
int x;
do {
x = st.top();
st.pop();
inStack[x] = false;
newScc.push_back(x);
} while (x != node);
scc.push_back(newScc);
}
}
inline void stronglyConnectedComponentsWithTarjan() {
memset(inStack, false, sizeof(inStack));
for (int i = 1; i <= V; ++ i) {
if (value[i] == 0) {
dfs(i);
}
}
}
inline void printResult() {
out << scc.size() << '\n';
for (vector <vector <int>>::iterator it = scc.begin(); it != scc.end(); ++ it) {
for (vector <int>::iterator jt = (*it).begin(); jt != (*it).end(); ++ jt) {
out << *jt << ' ';
}
out << '\n';
}
}
int main() {
readAndBuild();
stronglyConnectedComponentsWithTarjan();
printResult();
return 0;
}