Pagini recente » Cod sursa (job #2772696) | Cod sursa (job #728202) | Cod sursa (job #2170027) | Cod sursa (job #2819576) | Cod sursa (job #786456)
Cod sursa(job #786456)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
long n, m;
struct edge{
long to;
edge *next;
};
struct node{
long index, lowlink;
bool inStack;
edge *neigh;
node() : index(-1), lowlink(-1), neigh(NULL), inStack(false){}
};
node graf[100001];
void 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){
graf[nod].index = index;
graf[nod].lowlink = index;
index++;
S.push(nod);
graf[nod].inStack = true;
edge *p = graf[nod].neigh;
while(p){
if(graf[p->to].index == -1){
// not yet visited
proc(p->to);
graf[nod].lowlink = min(graf[nod].lowlink, graf[p->to].lowlink);
}
else if(graf[p->to].inStack){
graf[nod].lowlink = min(graf[nod].lowlink, graf[p->to].index);
}
}
if(graf[nod].index == graf[nod].lowlink){
vector<long> comp;
while(S.top() != nod){
long w = S.top();
S.pop();
graf[w].inStack = false;
comp.push_back(w);
}
S.pop();
graf[nod].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;
}