Pagini recente » Monitorul de evaluare | Cod sursa (job #761684) | Cod sursa (job #1052549) | Cod sursa (job #1241953) | Cod sursa (job #2642714)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int const NMAX = 1e5;
int n, m;
vector<int> g[1 + NMAX];
vector<int> scc[1 + NMAX];
int nComp;
stack<int> st;
int time1[1 + NMAX]; //blue label, the time at which we first landed on the node
int lowLink[1 + NMAX]; //red label, the lowest time of a node we could reach from i
int t = 0;
bool onStack[1 + NMAX];
void tarjan(int from) {
t++;
time1[from] = t;
lowLink[from] = t;
st.push(from);
onStack[from] = true;
for(int to : g[from]) {
if(time1[to] == 0) {
tarjan(to);
lowLink[from] = min(lowLink[from], lowLink[to]);
} else if(onStack[to]) {
lowLink[from] = min(lowLink[from], lowLink[to]);
}
}
if(lowLink[from] == time1[from]) {
//cout << "1\n";
while(!st.empty() && lowLink[from] <= lowLink[st.top()]) {
scc[nComp].push_back(st.top());
st.pop();
}
//cout << "2\n";
nComp++;
}
}
int main(){
in >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b;
in >> a >> b;
g[a].push_back(b);
}
for(int i = 1; i <= n; i++) {
if(time1[i] == 0) {
tarjan(i);
}
}
out << nComp << "\n";
for(int i = 0; i < nComp; i++) {
for(int j = 0; j < scc[i].size(); j++) {
out << scc[i][j] << " ";
}
out << "\n";
}
}