Cod sursa(job #499757)

Utilizator mika17Mihai Alex Ionescu mika17 Data 10 noiembrie 2010 19:37:04
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#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();
}