Cod sursa(job #1767728)
Utilizator | Meriniuc 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;
}