Pagini recente » Cod sursa (job #3235965) | Cod sursa (job #2421814) | Cod sursa (job #1477108) | Cod sursa (job #829264) | Cod sursa (job #2925958)
/*
Pentru a rezolva aceasta problema o sa folosim algoritmul Plus-Minus. Pentru fiecare nod x care nu a fost inca
plasat intr-o componenta tare conexa o sa facem urmatorii pasi:
- determinam toate nodurile la care putem ajunge plecand de la nodul x, marcand aceste noduri cu "plus"
- determinam toate nodurile din care putem ajunge in x, folosind graful transpus si le marcam cu "minus"
- la final o sa alegem nodurile care sunt marcate atat cu "plus", cat si cu "minus" ca facand parte din aceeasi
componenta tare conexa cu un nod x
Complexitate O(V+E), deoarece folosim lista de adiacenta pentru a memora graful
*/
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack<int> st;
vector<int> viz;
vector<int> disc_time;
vector<int> low_time;
vector<bool> inStack;
vector<vector<int>> rez;
void add(int x, int y, vector<int> adj[]){
adj[x].push_back(y);
}
void Tarjan(int node, vector<int> adj[]){
static int time = 0;
disc_time[node] = low_time[node] = ++time;
st.push(node);
inStack[node] = true;
for(int i=0;i<adj[node].size();i++){
if(disc_time[adj[node][i]] == -1){
Tarjan(adj[node][i], adj);
low_time[node] = min(low_time[node], low_time[node[adj][i]]);
}else if(inStack[adj[node][i]] == true){
low_time[node] = min(low_time[node], disc_time[adj[node][i]]);
}
}
vector<int> x;
if(disc_time[node] == low_time[node]){
while(st.top() != node){
x.push_back(st.top());
inStack[st.top()] = false;
st.pop();
}
x.push_back(st.top());
inStack[st.top()] = false;
st.pop();
sort(x.begin(), x.end());
rez.push_back(x);
}
}
int main(){
ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);
long n,m;
fin>>n>>m;
vector<int> adj[n+1];
long x,y;
for(int i=0;i<m;i++)
{
fin>>x>>y;
add(x,y,adj);
}
viz = vector<int> (n+1, 0);
disc_time = vector<int> (n+1, -1);
low_time = vector<int> (n+1, -1);
inStack = vector<bool> (n+1, false);
for(int i=1;i<=n;i++){
if(disc_time[i] == -1){
Tarjan(i, adj);
}
}
fout<<rez.size()<<endl;
for(int i=rez.size()-1;i>=0;i--)
{
for(int j=0;j<rez[i].size();j++)
{
fout<<rez[i][j]<<" ";
}
fout<<endl;
}
fin.close();
fout.close();
}