Pagini recente » Cod sursa (job #4837) | Cod sursa (job #2096870) | Cod sursa (job #1953067) | Cod sursa (job #890032) | Cod sursa (job #273450)
Cod sursa(job #273450)
#include <stack>
#include <vector>
#include <bitset>
#include <fstream>
#include <sstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100000, BUF_SIZE = 2000000;
typedef vector<int> :: iterator pint;
vector<int> G[NMAX], CTC[NMAX];
stack<int> S;
int N,M,num,nrc,low[NMAX],pre[NMAX];
bitset<NMAX> instk;
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) {
ss>>x>>y;
--x, --y;
G[x].push_back(y);
}
}
void df(int k) {
pre[k] = low[k] = ++num;
S.push(k); instk[k] = 1;
for(pint p = G[k].begin(); p != G[k].end(); ++p) {
if(!pre[*p]) df(*p);
if(instk[*p]) low[k] = min(low[k],low[*p]);
}
if(pre[k] == low[k]) {
int t;
do {
t = S.top();
S.pop(); instk[t] = 0;
CTC[nrc].push_back(t);
}
while (t != k);
++nrc;
}
}
void comp() {
for(int i=0;i<N;++i)
if(!pre[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();
}