Pagini recente » Cod sursa (job #2491563) | Cod sursa (job #2182813) | Cod sursa (job #2318517) | Cod sursa (job #186271) | Cod sursa (job #786460)
Cod sursa(job #786460)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
#define min(a, b) ((a)<(b)?(a):(b))
long n, m;
struct edge{
long to;
edge *next;
};
struct node{
long index, lowlink;
bool inStack;
edge *neigh;
node() : index(-1), lowlink(-1), inStack(false), neigh(NULL){}
};
node graf[100001];
void inline add_edge(long from, long to){
edge *e = new edge;
e->to = to;
e->next = graf[from].neigh;
graf[from].neigh = e;
}
stack<long> S;
vector<vector<long> > sol;
long index = 0;
void proc(long nod){
node& cur = graf[nod];
cur.index = index;
cur.lowlink = index;
index++;
S.push(nod);
cur.inStack = true;
edge *p = cur.neigh;
while(p){
node& w = graf[p->to];
if(w.index == -1){
// not yet visited
proc(p->to);
cur.lowlink = min(cur.lowlink, w.lowlink);
}
else if(graf[p->to].inStack){
cur.lowlink = min(cur.lowlink, w.index);
}
p = p->next;
}
if(cur.index == cur.lowlink){
vector<long> comp;
while(S.top() != nod){
long w = S.top();
S.pop();
graf[w].inStack = false;
comp.push_back(w);
}
S.pop();
cur.inStack = false;
comp.push_back(nod);
sol.push_back(comp);
}
}
int main(){
ifstream f("ctc.in");
f >> n >> m;
long u, v;
for(int i=0; i<m; i++){
f >> u >> v;
add_edge(u, v);
}
f.close();
for(int i=1; i<=n; i++){
if(graf[i].index == -1){
proc(i);
}
}
ofstream g("ctc.out");
g << sol.size() << endl;
for(vector<vector<long> >::iterator it = sol.begin(); it != sol.end(); it++){
for(vector<long>::iterator it1 = it->begin(); it1 != it->end(); it1++){
g << *it1 << " ";
}
g << endl;
}
g.close();
return 0;
}