Pagini recente » Cod sursa (job #2075056) | Cod sursa (job #411817) | Cod sursa (job #490025) | Cod sursa (job #1837677) | Cod sursa (job #2956980)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <stack>
#include <algorithm>
using namespace std;
class Graph{
int n, m;
std::vector<std::vector<std::pair<int, int>>> graph;
std::vector<std::vector<int>> ctc;
std::vector<int> father;
std::vector<int> distance;
std::vector<int> lowlink;
std::vector<int> id;
std::vector<bool> visited;
std::stack<int> s;
int totalCost;
int index;
void dfs(const int k){
visited[k] = true;
for (const int node : getNeighbors(k)){
if ( !visited[node] ){
father[node] = k;
dfs(node);
}
}
s.push(k);
}
void bfs(const int start){
std::queue<int> q;
q.push(start);
visited[start] = true;
distance[start] = 0;
while (!q.empty()){
int node = q.front();
q.pop();
for (int neighbor : getNeighbors(node)){
if (!visited[neighbor]){
visited[neighbor] = true;
distance[neighbor] = distance[node] + 1;
father[neighbor] = node;
q.push(neighbor);
}
}
}
}
struct edge{
int cost, x, y;
bool operator<(const edge o) const{
return ((this->cost) > o.cost);
}
};
void dijkstra(const int start){
distance.assign(n+1, 0x7fffffff);
std::queue<std::pair<int, int>> q;
q.push({0, start});
distance[start] = 0;
while (!q.empty()){
int currentNode = q.front().second;
q.pop();
for (const auto &node : getNeighborsWithWeight(currentNode)){
if(distance[currentNode] + node.second < distance[node.first])
{
distance[node.first] = distance[currentNode] + node.second;
q.push({-distance[node.first], node.first});
}
}
}
}
void tarjan(int k){
visited[k] = true;
lowlink[k] = id[k] = index++; // id-ul reprezinta la al catelea nod in parcurgere am ajuns
s.push(k); // adaug pe stiva nodul la care sunt
for (const int x : getNeighbors(k)){ // parcurg vecinii lui k
if( !id[x] ) // daca id-ul este 0, atunci nodul este nevizitat
tarjan(x), lowlink[k] = min(lowlink[k], lowlink[x]); // DFS + minimul dintre nodul curent(k) si vecinul sau(x) cand vine vorba de label
else if( visited[x] ) // daca nodul vecin(x) este vizitat si se afla pe stiva, atunci nodul curent ia valoarea minima dintre label-ul curent si label-ul vecinului sau(x)
lowlink[k] = min(lowlink[k], id[x]);
}
if(id[k] == lowlink[k]){ // daca label-ul (id-ul cel mai mic din componenta conexa) corespunde id-ului, atunci am descoperit componenta tare conexa
std::vector<int> tmp;
while(s.top() != k) // golesc toate elementele asociate CTC-ului din stiva
visited[s.top()] = false, tmp.push_back(s.top()) , s.pop();
visited[s.top()] = false, tmp.push_back(s.top()), s.pop(); // construiesc un vector temporar care contine nodurile din CTC
ctc.push_back(tmp); // Adaug vectorul obtinut la solutie
tmp.clear();
}
}
public:
explicit Graph(const int n = 0){
this -> n = n;
index = totalCost = m = 0;
graph.resize(n+1);
father.resize(n+1);
distance.resize(n+1);
visited.resize(n+1);
lowlink.resize(n+1);
id.resize(n+1);
ctc.clear();
}
void addEdge(const int x, const int y, const int cost = 1){
graph[x].push_back({y, cost});
++m;
}
int getEdgeWeight(const int x, const int y) const {
for (const auto& neighbor : graph[x]) {
if (neighbor.first == y) {
return neighbor.second;
}
}
return (int)0x80000000;
}
std::vector<int> getNeighbors(const int x) const {
std::vector<int> neighbors;
for (const auto& neighbor : graph[x]) {
neighbors.push_back(neighbor.first);
}
return neighbors;
}
std::vector<std::pair<int, int>> getNeighborsWithWeight(const int x) const {
return graph[x];
}
std::stack<int> topologicalSort() {
visited.assign(n+1, false);
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i);
}
}
return s;
}
void removeEdge(const int x, const int y){
for (auto it = graph[x].begin(); it != graph[x].end(); ++it) {
if (it -> first == y) {
graph[x].erase(it);
--m;
return;
}
}
}
void removeNode(const int x){
for (int i = 1; i <= n; ++i) {
removeEdge(i, x);
removeEdge(x, i);
}
graph[x].clear();
--n;
}
std::vector<std::pair<int, int>> MST(int x){
std::vector<std::pair<int, int>> mst;
visited.assign(n+1, false);
visited[x] = true;
std::priority_queue<edge> q;
for(auto e : getNeighborsWithWeight(x)) {
edge V{e.second, x, e.first};
q.push(V);
}
while (!q.empty()){
edge k = q.top();
q.pop();
if(visited[k.y] == 0) {
mst.push_back({k.x, k.y});
totalCost += k.cost;
visited[k.y] = true;
for (auto e: graph[k.y]) {
edge V{e.second, k.y, e.first};
q.push(V);
}
}
}
return mst;
}
int getCost() const {
return totalCost;
}
int getShortestPathFromTo(const int from, const int to){
dijkstra(from);
return distance[to];
}
std::vector<int> getDistancesFrom(const int from){
dijkstra(from);
return distance;
}
int howManyCC(){
int count = 0;
visited.assign(n+1, false);
for (int i = 1; i <= n; ++i)
if(!visited[i]) {
dfs(i);
++count;
}
return count;
}
std::vector<std::vector<int>> CTC(){
lowlink.resize(n+1, 0);
id.resize(n+1, 0);
index = 1;
ctc.clear();
for (int i = 1; i <= n; ++i) {
if( !id[i] )
tarjan(i);
}
return ctc;
}
};
int main() {
ifstream in("ctc.in");
int n, m;
in >> n >> m;
Graph g(n);
while (m--){
int x, y;
in >> x >> y;
g.addEdge(x, y);
}
in.close();
ofstream out("ctc.out");
auto sol = g.CTC();
out << sol.size() << '\n';
for (auto x : sol) {
sort(x.begin(), x.end()); // sortez pentru ca nodurile din CTC sa fie prezentate in ordine crescatoare
for (auto y: x) {
out << y << ' ';
}
out << '\n';
}
out.close();
return 0;
}