Pagini recente » Cod sursa (job #2378997) | Cod sursa (job #1675319) | Cod sursa (job #2338771) | Cod sursa (job #2306311) | Cod sursa (job #2345147)
#include <stack>
#include <vector>
#include <fstream>
#define NMAX 100010
using std::stack;
using std::vector;
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int n, m;
vector<int> ad[NMAX];
int ids[NMAX];
int low[NMAX];
int id;
stack<int> st;
bool onStack[NMAX];
int nrComp;
vector<int> comp[NMAX];
void dfs(int node) {
st.push(node);
onStack[node] = true;
ids[node] = low[node] = ++id;
for (int i = 0; i < (int) ad[node].size(); i++) {
int nghb = ad[node][i];
if (!ids[nghb]) {
dfs(nghb);
if (low[nghb] < low[node])
low[node] = low[nghb];
}
else if (onStack[nghb] && low[nghb] < low[node])
low[node] = low[nghb];
}
if (ids[node] == low[node]) {
while (true) {
int top = st.top();
st.pop();
onStack[top] = false;
low[top] = ids[node];
comp[nrComp].push_back(top);
if (top == node)
break;
}
nrComp++;
}
}
int main() {
int a, b;
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> a >> b;
ad[a].push_back(b);
}
for (int i = 1; i <= n; i++)
if (!ids[i])
dfs(i);
fout << nrComp << '\n';
for (int i = 0; i < nrComp; i++) {
for (int j = 0; j < (int) comp[i].size(); j++)
fout << comp[i][j] << ' ';
fout << '\n';
}
fout.close();
return 0;
}