Cod sursa(job #273450)

Utilizator mika17Mihai Alex Ionescu mika17 Data 8 martie 2009 16:45:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#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();
}