Pagini recente » Cod sursa (job #290657) | Cod sursa (job #2268783) | Cod sursa (job #24171) | Cod sursa (job #165185) | Cod sursa (job #2857443)
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
#define N 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector < vector <int> > g, cmp;
vector <int> low, dist;
bitset <N> viz, instack;
stack <int> st;
int n, m, nrc;
int timp;
void citire()
{
fin>>n>>m;
g = vector < vector <int> > (n+2);
dist = low = vector <int> (n+2);
int x, y;
for (int i=1; i<=m; ++i)
{
fin>>x>>y;
g[x].push_back(y);
}
}
void dfs(int x)
{
viz[x]=1;
dist[x]=low[x]=++timp;
st.push(x); instack[x]=1;
for (auto y:g[x])
if (viz[y])
{
if (instack[y]) low[x]=min(low[x], dist[y]);
}
else
{
dfs(y);
low[x]=min(low[x], low[y]);
}
if (low[x]==dist[x])
{
nrc++;
cmp.push_back(vector <int> (0));
while (st.top()!=x)
{
cmp[nrc-1].push_back(st.top());
instack[st.top()]=0;
st.pop();
}
cmp[nrc-1].push_back(st.top());
instack[st.top()]=0;
st.pop();
}
}
void solve()
{
for (int i=1; i<=n; ++i)
if (!viz[i]) dfs(i);
fout<<nrc<<'\n';
for (int i=0; i<nrc; ++i)
{
for (auto y:cmp[i]) fout<<y<<' ';
fout<<'\n';
}
}
int main()
{
citire();
solve();
return 0;
}