Pagini recente » Cod sursa (job #3243157) | Cod sursa (job #3243151)
#include <fstream>
#include <stack>
#include <vector>
#define NMAX 100000
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int>edge[NMAX + 1];
stack<int>st;
vector<int>componente[NMAX + 1];
int nrComp;
struct type_node{
int d, l;
bool isOnStack;
vector<int>edge;
}nodes[NMAX + 1];
int timp;
void dfs(int nod) {
st.push(nod);
nodes[nod].d = nodes[nod].l = ++timp;
nodes[nod].isOnStack = 1;
for(auto copil : edge[nod]) {
if(nodes[copil].d == 0) {
dfs(copil);
}
if(nodes[copil].isOnStack) {
nodes[nod].l = min(nodes[nod].l, nodes[copil].l);
}
}
if(nodes[nod].l == nodes[nod].d) {
nrComp++;
while(st.top() != nod) {
componente[nrComp].push_back(st.top());
nodes[st.top()].isOnStack = 0;
st.pop();
}
componente[nrComp].push_back(st.top());
nodes[st.top()].isOnStack = 0;
st.pop();
}
}
int main() {
int n, m, a, b;
cin>>n>>m;
while(m--) {
cin>>a>>b;
edge[a].push_back(b);
}
dfs(1);
cout<<nrComp<<"\n";
for(int i = 1; i <= nrComp; i++) {
for(int j = 0; j < componente[i].size(); j++) {
cout<<componente[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}