Pagini recente » Cod sursa (job #2435468) | Cod sursa (job #200378) | Cod sursa (job #1473816) | Cod sursa (job #1508145) | Cod sursa (job #499757)
Cod sursa(job #499757)
#include <stack>
#include <vector>
#include <bitset>
#include <fstream>
#include <sstream>
using namespace std;
typedef vector<int> :: iterator pint;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100000, BUF_SIZE = 2000000;
vector<int> G[NMAX], CTC[NMAX];
stack<int> S;
int N,M,num,nrc,low[NMAX],d[NMAX],f[NMAX]; //num = timestamp, nrc = # or SCCs,
bitset<NMAX> instack;
char buf[BUF_SIZE];
void readGraph() {
fin>>N>>M;
//fin.get(buf,BUF_SIZE,-1);
//stringstream ss(buf);
for(int x,y,i=0;i<M;++i) {
fin>>x>>y;//ss>>x>>y;
--x, --y;
G[x].push_back(y);
}
}
void df(int k) {
d[k] = low[k] = ++num;
S.push(k); instack[k] = 1;
for(pint p = G[k].begin(); p != G[k].end(); ++p) {
if(!d[*p]) {//tree-edge
df(*p);
low[k] = min(low[k],low[*p]);
}
else if(f[k] > 0 || (f[k] > 0 && instack[*p])) //back-edge OR cross-edge
low[k] = min(low[k],d[*p]);
}
if(d[k] == low[k]) {
int t;
do {
t = S.top();
S.pop(); instack[t] = 0;
CTC[nrc].push_back(t);
}
while (t != k);
++nrc;
}
f[k] = ++num;
}
void comp() {
for(int i=0;i<N;++i)
if(!d[i]) df(i);
}
void printSol() {
fout<<nrc<<'\n';
for(int i = 0; i < nrc; ++i) {
for(pint p = CTC[i].begin(); p != CTC[i].end(); ++p)
fout<<*p + 1<<' ';
fout<<'\n';
}
}
int main() {
readGraph();
comp();
printSol();
}