Pagini recente » Cod sursa (job #1061077) | Cod sursa (job #942782) | Cod sursa (job #193996) | Cod sursa (job #2638326) | Cod sursa (job #2808323)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack < int > st;
bool in_stack[100005];
int n,m;
vector < int > v[100005];
int x,y;
int viz[100005];
int low[100005];
int nr_ctc;
vector < int > ctcs[100005];
int ids[100005],id;
void read_graph() {
f >> n >> m;
for (int i=1;i<=m;i++) {
f >> x >> y;
v[x].push_back(y);
}
}
void dfs(int nod) {
st.push(nod);
in_stack[nod]=1;
viz[nod]=1;
low[nod]=++id;
ids[nod]=id;
for (auto k:v[nod]) {
if (viz[k]==0) {
dfs(k);
}
if (in_stack[k]==1) {
low[nod]=min(low[nod],low[k]);
}
}
if (low[nod]==ids[nod]) {
nr_ctc++;
ctcs[nr_ctc].push_back(nod);
while (st.top()!=nod) {
in_stack[st.top()]=0;
ctcs[nr_ctc].push_back(st.top());
st.pop();
}
in_stack[nod]=0;
st.pop();
}
}
void tarjan() {
for (int i=1;i<=n;i++) {
if (viz[i]==0) {
dfs(i);
}
}
}
void show() {
g << nr_ctc << '\n';
for (int i=1;i<=nr_ctc;i++) {
for (auto k:ctcs[i]) {
g << k << " ";
}
g << '\n';
}
}
int main()
{
read_graph();
tarjan();
show();
return 0;
}