Pagini recente » Cod sursa (job #1171698) | Cod sursa (job #3123345) | Cod sursa (job #232756) | Cod sursa (job #3126670) | Cod sursa (job #1373732)
///TARJAN
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <limits>
#include <list>
using namespace std;
const int INF = numeric_limits<int>::max();
list<list<int> > answ;;
struct Node {
int ind, low;
bool inQ;
Node() {
ind = low = INF;
inQ = false;
}
};
void findComp(vector<vector<int> >& adjList, vector<Node>& nds,
stack<int>& s, int v, int& ind) {
nds[v].ind = ind;
nds[v].low = ind;
nds[v].inQ = true;
s.push(v);
++ind;
int w;
for(int i=0; i<adjList[v].size(); ++i) {
w = adjList[v][i];
if(nds[w].ind == INF) {
findComp(adjList, nds, s, w, ind);
nds[v].low = min(nds[v].low, nds[w].low);
} else
if(nds[w].inQ)
nds[v].low = min(nds[v].low, nds[w].ind);
}
///if v is a root of a strongly connected component
if(nds[v].low == nds[v].ind) {
list<int> comp;
do {
w = s.top();
s.pop();
nds[w].inQ = false;
comp.push_back(w);
} while(v != w);
answ.push_back(comp);
}
}
int main() {
ifstream inStr("ctc.in");
ofstream outStr("ctc.out");
int N, M;
inStr >> N >> M;
vector<vector<int> > adjList(N);
int fr, to;
for(int i=0; i<M; ++i) {
inStr >> fr >> to;
adjList[--fr].push_back(--to);
}
vector<Node> nds(N, Node());
stack<int> s;
int ind = 0;
for(int i=0; i<N; ++i)
if(nds[i].ind == INF)
findComp(adjList, nds, s, i, ind);
outStr << answ.size() << '\n';
for(list<list<int> >::iterator i=answ.begin(); i!=answ.end(); ++i) {
for(list<int>::iterator j=i->begin(); j!=i->end(); ++j)
outStr << *j+1 << ' ';
outStr << '\n';
}
return 0;
}