Cod sursa(job #2302170)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 decembrie 2018 21:37:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
#define N 100001
#define Min(a, b)  ((a) < (b) ? (a) : (b))
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 tarjan(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)
            tarjan(*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)
            tarjan(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";
    }
}