Pagini recente » Cod sursa (job #294133) | Cod sursa (job #423609) | Cod sursa (job #1910195) | Cod sursa (job #2087716) | Cod sursa (job #2209286)
#include <bitset>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100005
vector<vector<int> > sol;
vector<int> G[NMAX];
int comp[NMAX];
int level[NMAX];
stack<int> st;
bool inStack[NMAX];
int n, m, x, y;
int indexi;
void dfs(int node){
comp[node] = ++indexi;
level[node] = indexi;
inStack[node] = true;
st.push(node);
indexi++;
for(auto next : G[node]){
if(!comp[next])
{
dfs(next);
level[node] = min(level[node], level[next]);
}
else if(inStack[next]) level[node] = min(level[node], level[next]);
}
if(comp[node] == level[node]){
sol.push_back(vector<int>());
int v;
do{
v = st.top();
sol[sol.size() - 1].push_back(v);
inStack[v] = false;
st.pop();
}while(v != node);
}
}
int main()
{
ifstream fin("ctc.in");
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> x >> y;
G[x].push_back(y);
}
fin.close();
for(int i = 1; i <= n; i++){
if(comp[i] == 0)
dfs(i);
}
ofstream fout("ctc.out");
fout << sol.size()<< '\n';
for(int i = 0; i < sol.size(); i++){
for(int j = 0; j < sol[i].size(); j++){
fout << sol[i][j] << ' ';
}
fout << '\n';
}
fout.close();
return 0;
}