Pagini recente » Cod sursa (job #1368356) | Cod sursa (job #219264) | Cod sursa (job #1897407) | Cod sursa (job #2276595) | Cod sursa (job #3218806)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;
void be(int &n, vector<vector<int>> &adj) {
ifstream fin("ctc.in");
int m;
fin >> n >> m;
adj.resize(n+1);
while(m--) {
int u, v;
fin >> u >> v;
adj[u].push_back(v);
}
}
vector<vector<int>> ans;
void SCC(int from, int n, vector<int> &disc, vector<int> &low, vector<bool> &onstack, vector<vector<int>> &adj, stack<int> &st, int &time) {
disc[from]=low[from]=time;
time++;
onstack[from]=true;
st.push(from);
for(auto it : adj[from]) {
if(disc[it]==-1) {
SCC(it, n, disc, low, onstack, adj, st, time);
low[from]=min(low[from], low[it]);
} else if(onstack[it]) {
low[from]=min(low[from], disc[it]);
}
}
if(low[from]==disc[from]) {
vector<int> comp;
while(from!=st.top()) {
comp.push_back(st.top());
onstack[st.top()]=false;
st.pop();
}
comp.push_back(st.top());
onstack[st.top()]=false;
st.pop();
ans.push_back(comp);
}
}
int main() {
int n;
vector<vector<int>> adj;
be(n, adj);
vector<int> disc(n+1, -1);
vector<int> low(n+1, -1);
vector<bool> onstack(n+1);
stack<int> st;
int time=0;
for(int i=1; i<=n; i++) {
if(disc[i]==-1) {
SCC(i ,n, disc, low, onstack, adj, st, time);
}
}
ofstream fout("ctc.out");
fout << ans.size() << '\n';
for(int i=0; i<ans.size(); i++) {
for(auto it : ans[i]) {
fout << it << ' ';
}
fout << '\n';
}
return 0;
}