Cod sursa(job #2125653)

Utilizator alex99Chelba Alexandru alex99 Data 8 februarie 2018 17:02:46
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g1("ctc.out");
int n,*viz,m;
class graph
{
public:
    int n,*viz;
    stack<int> s;
    vector<int> *v;
    graph(int n);
    void adauga(int x, int y);
    void dfs(int k, bool viz[]);
    void dfsutil(int k, bool viz[]);
    graph ogl();
    void afis();
};
graph::graph(int n)
{
    this->n=n;
    v=new vector<int>[n];
}
void graph::adauga(int x, int y)
{
    v[x].push_back(y);
}
void graph::dfsutil(int k, bool viz[])
{
    viz[k]=1;
    g1<<k+1<<" ";
    for(int i=0;i<v[k].size();i++)
    if(viz[v[k][i]]==0) dfsutil(v[k][i],viz);
}
void graph::dfs(int k, bool viz[])
{
    viz[k]=1;
    for(int i=0;i<v[k].size();i++)
        if(viz[v[k][i]]==0)
        dfs(v[k][i],viz);
    s.push(k);
}
graph graph::ogl()
{
    graph g(n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<v[i].size();j++)
            g.v[v[i][j]].push_back(i);
    }
    return g;
}
void graph::afis()
{
    bool *viz;
    viz=new bool[n];
    for(int i=0;i<n;i++)
        viz[i]=0;
    for(int i=0;i<n;i++)
        if(viz[i]==0) dfs(i,viz);
    graph gr=ogl();
    for(int i=0;i<n;i++)
        viz[i]=0;
    int nr=0;
    while(s.size())
    {
        int nod=s.top();
        s.pop();
        if(viz[nod]==0)
        {
            gr.dfsutil(nod,viz);
            g1<<'\n';
            nr++;
        }
    }
}
int main()
{
    f>>n>>m;
    graph g(n);
    for(int i=0;i<m;i++)
    {
        int x,y;
        f>>x>>y;
        g.adauga(x-1,y-1);
    }
    g.afis();
    return 0;
}