Pagini recente » Cod sursa (job #2294854) | Cod sursa (job #1843598) | Cod sursa (job #1535513) | Cod sursa (job #148039) | Cod sursa (job #2121796)
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
using namespace std;
const int MAXN = 100005;
ifstream input("ctc.in");
ofstream output("ctc.out");
vector<int> graph[MAXN];
vector<vector<int>> components;
stack<int> st;
bitset<MAXN> inStack;
int n, m, index[MAXN], lowlink[MAXN], INDEX;
void readData() {
input >> n >> m;
int x, y;
for (int i = 0; i < m; i++) {
input >> x >> y;
graph[x].push_back(y);
}
}
void dfs(int node) {
index[node] = lowlink[node] = ++INDEX;
st.push(node);
inStack[node] = 1;
for (int y : graph[node]) {
if (!index[y]) {
dfs(y);
lowlink[node] = min(lowlink[node], lowlink[y]);
} else if (inStack[y]) {
lowlink[node] = min(lowlink[node], index[y]);
}
}
if (lowlink[node] == index[node]) {
int y;
vector<int> comp;
do {
y = st.top();
st.pop();
inStack[y] = 0;
comp.push_back(y);
} while (y != node);
components.push_back(comp);
}
}
void tarjan() {
for (int i = 1; i <= n; i++)
if (!index[i]) {
dfs(i);
}
}
void printComponents() {
output << components.size() << '\n';
for (auto c : components) {
for (int node : c)
output << node << ' ';
output << '\n';
}
}
int main() {
readData();
tarjan();
printComponents();
return 0;
}