Cod sursa(job #2237834)

Utilizator danielsociuSociu Daniel danielsociu Data 3 septembrie 2018 14:13:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>
#include <stack>
std::ifstream cin("ctc.in");
std::ofstream cout("ctc.out");
#define maxn 200020
#define inf 50000
#define Min(a,b) (a<b)?a:b
using namespace std;
vector <int> muc[maxn],com;
vector <vector <int>> C;
int viz[maxn],in_stack[maxn],lowlink[maxn];
stack <int> S;
int N,M,indecs=1;

void tarjan(int x){
    viz[x]=lowlink[x]=indecs;
    indecs++;
    S.push(x); in_stack[x]=1;
    for(vector <int>::iterator it=muc[x].begin();it!=muc[x].end();it++){
        if(!viz[*it]){
            tarjan(*it);
            lowlink[x]=Min(lowlink[x],lowlink[*it]);
        }else if(in_stack[*it])
            lowlink[x]=Min(lowlink[x],lowlink[*it]);
    }
    if(viz[x]==lowlink[x]){
        com.clear();
        int nod;
        do{
            com.push_back(nod=S.top());
            S.pop();
            in_stack[nod]=0;
        }while(x!=nod);
        C.push_back(com);
    }
}

int main()
{
    int x,y;
    cin>>N>>M;
    for(;M--;){
        cin>>x>>y;
        muc[x].push_back(y);
    }
    for(int i=1;i<=N;i++)
        if(!viz[i])
            tarjan(i);

      cout<<C.size()<<'\n';
      for(unsigned int i=0;i<C.size();i++){
        for(vector <int>::iterator it=C[i].begin();it!=C[i].end();it++)
            cout<<*it<<' ';
        cout<<'\n';
    }
}