Pagini recente » Cod sursa (job #2858112) | Cod sursa (job #2738589) | Cod sursa (job #812874) | Cod sursa (job #2662868) | Cod sursa (job #1423255)
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#define N 100002
using namespace std;
bool viz[N], in_stack[N];
vector <int> v[N];
stack <int> st;
int low_level[N], sol[2*N], poz, nr_ctc;
void dfs(int nd, int niv)
{
st.push(nd);
in_stack[nd] = 1;
low_level[nd] = niv;
viz[nd] = 1;
for(vector<int>::iterator it = v[nd].begin(); it!=v[nd].end(); ++it)
{
if(!viz[*it])
{
dfs(*it, niv+1);
low_level[nd] = min(low_level[nd], low_level[*it]);
}
else if(in_stack[*it])
low_level[nd] = min(low_level[nd], low_level[*it]);
}
/*nodul este radacina a unei componente tare conexa*/
if(niv == low_level[nd])
{
++nr_ctc;
while(st.top() != nd)
{
sol[poz++] = st.top();
in_stack[st.top()] = 0;
st.pop();
}
sol[poz++] = st.top();
in_stack[st.top()] = 0;
st.pop();
/*marchez sfarsitul primei comonente*/
sol[poz++] = -1;
}
}
int main()
{
int i, n, m, x, y;
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> n >> m;
for(i=0; i<m; ++i)
{
f >> x >> y;
v[x].push_back(y);
}
for(i=1; i<=n; ++i)
if(!viz[i]) dfs(i, 0);
g << nr_ctc << "\n";
for(i=0; i<poz; ++i)
{
while(i<poz && sol[i] != -1)
{
g << sol[i] << " ";
++i;
}
g<< "\n";
}
f.close();
g.close();
return 0;
}