Pagini recente » Cod sursa (job #2172497) | Cod sursa (job #254004) | Cod sursa (job #1173) | Cod sursa (job #1133695) | Cod sursa (job #2230807)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define UNDEF -1
int x,y,index,N,M;
int low[100005],idx[100005];
bool in_stack[100005];
stack<int> st;
vector<int> g[100005];
vector<vector<int> > result;
ifstream in("ctc.in");
ofstream out("ctc.out");
int min(int a,int b) {
return a<b?a:b;
}
void tarjan(int v) {
idx[v]=index;
low[v]=index;
index=index+1;
st.push(v);
in_stack[v]=true;
for (int u=0;u<g[v].size();u++) {
if (idx[g[v][u]]==UNDEF) {
tarjan(g[v][u]);
low[v]=min(low[v],low[g[v][u]]);
}
else if (in_stack[g[v][u]])
low[v]=min(low[v],idx[g[v][u]]);
}
if (idx[v]==low[v]) {
result.push_back(vector<int>());
int node;
do {
node=st.top();
st.pop();
in_stack[node]=false;
result[result.size()-1].push_back(node);
}while (v!=node);
}
}
void ctc() {
index=0;
for (int i=1;i<=N;i++)
if (idx[i]==UNDEF)
tarjan(i);
}
int main() {
in>>N>>M;
for (int i=1;i<=M;i++) {
in>>x>>y;
in_stack[x]=false; idx[x]=UNDEF; low[x]=0;
in_stack[y]=false; idx[y]=UNDEF; low[y]=0;
g[x].push_back(y);
}
ctc();
out<<result.size()<<"\n";
for (int i=result.size()-1;i>=0;i--) {
for (int j=result[i].size()-1;j>=0;j--)
out<<result[i][j]<<" ";
out<<"\n";
}
in.close();
out.close();
return 0;
}