Cod sursa(job #2302175)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 decembrie 2018 21:41:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include<fstream>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
#define N 100001
vector<int> adj[N],con,idx,lowlink,in_stack;
vector<vector<int>> C;
stack<int> S;
int indecs,n,i,j,x,y,cnt_edges;
void T(const int n,const vector<int> *adj)
{
    idx[n]=lowlink[n]=indecs;
    indecs++,S.push(n),in_stack[n]=1;
    vector<int>::const_iterator it;
    for(it=adj[n].begin();it!=adj[n].end();it++)
        if(idx[*it]==-1)
            T(*it,adj),lowlink[n]=min(lowlink[n],lowlink[*it]);
        else if(in_stack[*it])
            lowlink[n]=min(lowlink[n],lowlink[*it]);
    if(idx[n]==lowlink[n])
    {
        con.clear();
        int node;
        do
            con.push_back(node=S.top()),S.pop(),in_stack[node]=0;
        while(node!=n);
        C.push_back(con);
    }
}
int main(void)
{
    ifstream f("ctc.in");
    ofstream g("ctc.out");
    f>>n;
    for(f>>cnt_edges;cnt_edges>0;cnt_edges--)
        f>>x>>y,adj[x-1].push_back(y-1);
    idx.resize(n),lowlink.resize(n),in_stack.resize(n),idx.assign(n,-1),in_stack.assign(n,0);
    for(i=0;i<n;i++)
        if(idx[i]==-1)
            T(i,adj);
    g<<C.size()<<"\n";
    for(i=0;i<C.size();i++)
    {
        for(j=0;j<C[i].size();j++)
            g<<C[i][j]+1<<" ";
        g<<"\n";
    }
}