Pagini recente » Cod sursa (job #743779) | Cod sursa (job #417360) | Cod sursa (job #875157) | Cod sursa (job #1267295) | Cod sursa (job #1717660)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int dftime, n, m, tin[MAXN + 2], low[MAXN + 2], in_stk[MAXN + 2];
vector<int>comp;
vector<int>adj[MAXN + 2];
vector<vector<int>>allcomps;
stack<int>st;
bool vis[MAXN + 2];
void read() {
ifstream f("ctc.in");
f >> n >> m;
for(int i = 1, x, y; i <= m; ++i) {
f >> x >> y;
adj[x].push_back(y);
}
}
void get_scc(int nod) {
comp = vector<int>();
int curr;
do {
curr = st.top(), in_stk[curr] = false;
comp.push_back(curr);
st.pop();
}
while(!st.empty() && curr != nod);
allcomps.push_back(comp);
}
void dfs(int nod) {
tin[nod] = low[nod] = ++dftime;
in_stk[nod] = true;
vis[nod] = true;
st.push(nod);
for(auto current: adj[nod]) {
if(!vis[current]) {
dfs(current);
low[nod] = min(low[nod], low[current]);
}
else if(in_stk[current])
low[nod] = min(low[nod], tin[current]);
}
if(low[nod] == tin[nod])
get_scc(nod);
}
void solve() {
for(int i = 1; i <= n; ++i)
if(!vis[i])
dfs(i);
ofstream g("ctc.out");
g << allcomps.size() << '\n';
for(auto& current: allcomps) {
for(auto &iter: current)
g << iter << ' ';
g << '\n';
}
}
int main() {
read();
solve();
return 0;
}