Pagini recente » Cod sursa (job #2471785) | Cod sursa (job #903498) | Cod sursa (job #2956427) | Cod sursa (job #908976) | Cod sursa (job #3280919)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
#define cin in
#define cout out
const int N = 2e5 + 1;
vector<int> v[N];
vector<vector<int>> componente2;
stack<int> S;
int low[N], index[N], noduri , nr_componente;
bool in_stiva[N];
void dfs(int nod)
{
index[nod] = ++noduri;
low[nod] = index[nod];
S.push(nod);
in_stiva[nod] = 1;
for(auto &i : v[nod])
{
if(index[i] == 0)
{
dfs(i);
low[nod] = min(low[i],low[nod]);
}
else
{
if(in_stiva[i] != 0)
low[nod] = min(index[i], low[nod]);
}
}
vector<int> c1;
if(index[nod] == low[nod])
{
while(!S.empty())
{
int varf = S.top();
S.pop();
in_stiva[varf] = 0;
c1.push_back(varf);
if(varf == nod)
break;
}
componente2.push_back(c1);
nr_componente++;
}
}
signed main()
{
int n, M;
cin >> n >> M;
for (int i = 1, a, b; i <= M; i++)
{
cin >> a >> b;
v[a].push_back(b);
}
for(int i=1; i<=n; i++)
{
if(index[i] == 0)
dfs(i);
}
cout << nr_componente << '\n';
for(auto i : componente2){
for(auto j : i)
cout << j << ' ';
cout << '\n';
}
}