Pagini recente » Cod sursa (job #662325) | Cod sursa (job #1634545) | Cod sursa (job #2893595) | Cod sursa (job #1920359) | Cod sursa (job #2500130)
#include <fstream>
#include <vector>
#include <stack>
#include <cmath>
const int MAXN = 100000;
using namespace std;
ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );
int n, m, ans;
int id[1+MAXN+1], low[1+MAXN+1], lastId;
bool visited[1+MAXN+1];
bool inStack[1+MAXN+1];
stack<int> st;
vector<int> graph[1+MAXN+1], solution[1+MAXN+1];
void dfs(int node) {
visited[node] = true;
id[node] = low[node] = lastId++;
st.push(node);
inStack[node] = true;
for(auto it:graph[node]) {
if(!visited[it]) {
dfs(it);
low[node] = min(low[node], low[it]);
}
else if( inStack[it] ) {
low[node] = min(low[node], low[it]);
}
}
if(id[node] == low[node]) {
ans++;
bool found = false;
while(!found) {
found = (st.top() == node);
solution[ans].push_back(st.top());
inStack[st.top()] = false;
st.pop();
}
}
}
int main() {
fin>>n>>m;
for(int i=1; i<=m; i++) {
int x, y;
fin>>x>>y;
graph[x].push_back(y);
}
for(int i=1; i<=n; i++)
if(!visited[i]) {
dfs(i);
}
fout<<ans<<"\n";
for(int i=1; i<=ans; i++) {
for(auto it:solution[i]) {
fout<<it<<" ";
}
fout<<"\n";
}
return 0;
}