Pagini recente » Cod sursa (job #2703799) | Cod sursa (job #670526) | Cod sursa (job #1658483) | Cod sursa (job #592275) | Cod sursa (job #1936813)
#include<fstream>
#include<vector>
#include<stack>
#define DIM 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y, low[DIM], niv[DIM], f[DIM], nr, cod;
vector<int> v[DIM], sol[DIM];
stack<int> st;
void dfs( int nod ){ //tarjan
cod++;
niv[nod] = low[nod] = cod; //consider nodu ca fiind propria componenta tare conexa
st.push( nod );// adaug nodul in stiva
f[nod] = 1;
for( int i = 0; i < v[nod].size(); i++ ){
int vecin = v[nod][i];
//incerc sa vad daca nod nu cumva pot extinde componenta tare conexa a lui nod
if( niv[vecin] == 0 ){
dfs( vecin );
low[nod] = min( low[nod], low[vecin] );
}else{
if( f[vecin] == 1 ){
low[nod] = min( low[nod], low[vecin] );
}
}
}
if( low[nod] == niv[nod] ){ //insemna ca am format o componenta tare conexa din care face parte si nod
// ea este formata din nodurile din stiva pana la nod
nr++;
while( st.top() != nod ){
sol[nr].push_back( st.top() );
f[ st.top() ] = 0; //definitizez componenta tare conexa
st.pop();
}
sol[nr].push_back( st.top() );
st.pop();
}
return;
}
int main(){
fin >> n >> m;
for( int i = 1; i <= m; i++ ){
fin >> x >> y;
v[x].push_back(y);
}
//niv[nod] = reprezinta o codificare unica a lui nodsi un vector de frecventa daca nod se afla deja intr-o componenta tare conexa
// cu cat este mai mic cu atat consider ca este mai aproape de radacina componentei tare conexe
// ( cel mai mic dintr- o componenta repr radacina componentei )
//low[nod] = reprezinta cel mai aropiat nod ( codul unic ) de radacina componentei tare conexe din care face parte
//f[nod] = 0 daca consider ca e intr-o componenta tare conexa definitizata si 1 pt una in curs de definire
cod = 0;
for( int i = 1; i <= n; i++ ){
if( niv[i] == 0 ){
dfs(i);
}
}
fout << nr << "\n";
for( int i = 1; i <= nr; i++ ){
for( int j = 0; j < sol[i].size(); j++ ){
fout << sol[i][j] << " ";
}
fout << "\n";
}
return 0;
}