Pagini recente » Cod sursa (job #2107984) | Sebi | Istoria paginii utilizator/dumitrescutoma104 | Cod sursa (job #1273774) | Cod sursa (job #3295220)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 1e5 + 5;
int n, m, NrCtc,
cur_idx = 1, ///id-ul folosit pentru asocieri
idx[NMAX], ///id-ul nodului
lowlink[NMAX]; ///cel mai mic idx la care pot ajunge
vector<int> G[NMAX], ///Graful;
CTC[NMAX]; ///Componente conexe
bool ActivSt[NMAX];
stack<int> st;
void dfs(int nod) ///Tarjan
{
idx[nod] = cur_idx++;
lowlink[nod] = idx[nod];
ActivSt[nod] = 1;
st.push(nod);
for(const auto &i : G[nod])
if(!idx[i])
{
dfs(i);
lowlink[nod] = min(lowlink[nod], lowlink[i]);
}
else if(ActivSt[i])
lowlink[nod] = min(lowlink[nod], lowlink[i]);
if(lowlink[nod] == idx[nod])
{
NrCtc++;
int crt;
do
{
crt = st.top();
st.pop();
CTC[NrCtc].push_back(crt);
ActivSt[crt] = 0;
}while(crt != nod);
}
}
int main()
{
int i, x, y;
f >> n >> m;
for(i = 1; i <= m; ++i)
{
f >> x >> y;
G[x].push_back(y);
}
for(i = 1; i <= n; ++i)
if(!idx[i]) dfs(i);
g << NrCtc << '\n';
for(i = 1; i <= NrCtc; i++)
{
for(const auto &j : CTC[i])
g << j << ' ';
g << '\n';
}
f.close();
g.close();
return 0;
}