Cod sursa(job #1767728)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 29 septembrie 2016 17:24:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 5.43 kb
#include <fstream>
#include <stack>
#include <vector>
  
std::ifstream mama("ctc.in");
std::ofstream tata("ctc.out");
  
std::vector <int> v[100001];
std::vector <std::vector <int> > components;
std::stack <int> s;
  
int vindex[100001];
int l[100001];
bool onStack[100001];
int n;
int m;
int counterIndex;
  
    void
    go(int node)
{
        int vertex;
            int size;
              
                vindex[node] = counterIndex;
                    l[node] = counterIndex;
                        ++counterIndex;
                            s.push(node);
                                onStack[node] = true;
                                  
                                    for (int i = 0; i < (int)v[node].size(); ++i)
                                            {
                                                        if (not vindex[v[node][i]])
                                                                    {
                                                                                    go(v[node][i]);
                                                                                                if (l[node] > l[v[node][i]])
                                                                                                                {
                                                                                                                                    l[node] = l[v[node][i]];
                                                                                                                                                }
                                                                                                        }
                                                                else if (onStack[v[node][i]])
                                                                            {
                                                                                            if (l[node] > l[v[node][i]])
                                                                                                            {
                                                                                                                                l[node] = l[v[node][i]];
                                                                                                                                            }
                                                                                                    }
                                                                    }
                                      
                                        if (l[node] == vindex[node])
                                                {
                                                            components.push_back(std::vector <int> ());
                                                                    size = (int)components.size() - 1;
                                                                            do
                                                                                        {
                                                                                                        vertex = s.top();
                                                                                                                    s.pop();
                                                                                                                                onStack[vertex] = false;
                                                                                                                                            components[size].push_back(vertex);
                                                                                                                                                    } while (vertex != node);
                                                                                }
}
  
int main()
{
        mama >> n;
            mama >> m;
              
                for (int i = 0, a, b; i < m; ++i)
                        {
                                    mama >> a >> b;
                                            v[a].push_back(b);
                                                }
                  
                    counterIndex = 1;
                        for (int i = 1; i <= n; ++i)
                                {
                                            if (not vindex[i])
                                                        {
                                                                        go(i);
                                                                                }
                                                }
                          
                            tata << components.size() << '\n';
                              
                                for (const auto& comp : components)
                                        {
                                                    for (const auto& it : comp)
                                                                {
                                                                                tata << it << ' ';
                                                                                        }
                                                      
                                                            tata << '\n';
                                                                }
                                      
                                    return 0;
}