Pagini recente » Cod sursa (job #2360596) | Cod sursa (job #1706375) | Cod sursa (job #2840131) | Cod sursa (job #1446818) | Cod sursa (job #2928838)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void dfs(int x, vector<vector<int>> &v, stack<int> &st, vector<bool> &flag, vector<int> &id, vector<int> &low, int &curr, int &nr, vector<vector<int>> &valori)
{
st.push(x);
flag[x] = true;
curr++;
id[x] = curr;
low[x] = curr;
for(int i = 0; i < v[x].size(); i++)
{
if(id[v[x][i]] == -1)
{
dfs(v[x][i], v, st, flag, id , low, curr, nr, valori);
}
if(flag[v[x][i]] == true)
{
low[x] = min(low[x], low[v[x][i]]);
}
}
if(id[x] == low[x])
{
vector<int> aux;
int varf = -1;
while(varf != x)
{
varf = st.top();
aux.push_back(varf);
st.pop();
flag[varf] = false;
low[varf] = id[x];
}
nr++;
valori.push_back(aux);
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, a, b;
f >> n >> m;
vector<vector<int>> lista_adiacenta(n+1);
vector<bool> sflag(n+1, false);
vector<int> lowlink(n+1, 0);
vector<int> id(n+1, -1);
stack<int> st;
vector<vector<int>> valori;
int nr = 0;
for(int i = 0; i < m; i++)
{
f >> a >> b;
lista_adiacenta[a].push_back(b);
}
int curr = 0;
for(int i = 1; i < n; i++)
{
if(id[i] == -1)
{
dfs(i, lista_adiacenta, st, sflag, id, lowlink, curr, nr, valori);
}
}
g << nr << "\n";
for(int i = 0; i < valori.size(); i++)
{
for(int j = 0; j < valori[i].size(); j++)
{
g << valori[i][j] << " ";
}
g << "\n";
}
return 0;
}