Pagini recente » Cod sursa (job #253541) | Cod sursa (job #253860) | Cod sursa (job #1447486) | Cod sursa (job #1764670) | Cod sursa (job #2928770)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n;
class Solve {
vector<vector<int> > sol;
vector<vector<int> > lista;
int nr;
vector<int> f;
vector<int> s;
vector<int> low;
vector<int> id;
int top;
int idact;
void Dfs(int act){
s[++top] = act;
f[act] = 1;
id[act] = low[act] = ++idact;
for(auto next:lista[act])
{
if(id[next] == -1) Dfs(next);
if(f[next] == 1) {
if(low[act] > low[next]) low[act] = low[next];
}
}
if(id[act] == low[act])
{
vector<int> aux;
aux.push_back(act);
for(int j = top;;j--)
{
if(s[top] == act) {top--; break;}
aux.push_back(s[j]);
top--;
f[s[j]] = 2;
id[s[j]] = id[act];
}
sol.push_back(aux);
}
};
public:
vector<vector<int> > Tarjan(int nr, vector<vector<int> > &lista) {
this->lista = lista;
this->nr = nr;
for(int i = 0; i <= n; i++)
{
f.push_back(-1);
s.push_back(0);
id.push_back(-1);
low.push_back(100000);
}
top = -1;
idact = 0;
sol.clear();
for(int i = 1; i <= nr; i++)
{
if(f[i] == -1) Dfs(i);
}
/*for(auto x:sol)
{
for(auto y: x)
cout<<y<<' ';
cout<<'\n';
}*/
return sol;
}
};
vector<vector<int> > Citire()
{
int m, x, y;
fin>>n>>m;
vector<vector<int> > lista(n+1);
for(int i = 0; i < m; i++)
{
fin>>x>>y;
lista[x].push_back(y);
}
return lista;
}
int main() {
vector<vector<int> > v;
Solve a;
v = Citire();
v = a.Tarjan(n, v);
fout<<v.size()<<'\n';
for(auto x:v)
{
for(auto y: x)
fout<<y<<' ';
fout<<'\n';
}
return 0;
}