Pagini recente » Cod sursa (job #2792667) | Cod sursa (job #2815181) | Cod sursa (job #1877953) | Cod sursa (job #61696) | Cod sursa (job #2925943)
/*
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;
void add(int x, int y, vector<int> adj[]){
adj[x].push_back(y);
}
void dfs_stack(int node, vector<int> adj[]){
viz[node] = 1;
for(int i=0;i<adj[node].size();i++){
if(viz[adj[node][i]] == 0)
dfs_stack(adj[node][i], adj);
}
st.push(node);
}
void dfs_final(int node, vector<int> transpose[], int componenta){
viz[node] = componenta;
for(int i=0;i<transpose[node].size();i++){
if(viz[transpose[node][i]] == 0)
dfs_final(transpose[node][i], transpose, componenta);
}
}
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];
vector<int> transpose[n+1];
long x,y;
for(int i=0;i<m;i++)
{
fin>>x>>y;
add(x,y,adj);
add(y,x,transpose);
}
viz = vector<int> (n+1, 0);
int numar_componente = 0;
for(int i=1;i<=n;i++){
if(viz[i] == 0)
dfs_stack(i, adj);
}
viz = vector<int> (n+1, 0);
while(!st.empty()){
int x = st.top();
st.pop();
if(viz[x] == 0){
numar_componente += 1;
dfs_final(x, transpose, numar_componente);
}
}
fout<<numar_componente<<"\n";
for(int i=1;i<=numar_componente;i++){
for(int j=1;j<=n;j++)
if(viz[j] == i)
fout<<j<<" ";
fout<<"\n";
}
fin.close();
fout.close();
}