Pagini recente » Cod sursa (job #1767035) | Cod sursa (job #2294858) | Cod sursa (job #3351434) | Cod sursa (job #262991) | Cod sursa (job #3344389)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a, b, disc[100001], low[100001];
vector<int> graf[100001], rez[100001];
stack<int> st;
bool inStack[100001];
int timer=0, cnt;
void dfs(int nod)
{
timer++;//timp cand bagam nodul in stack
disc[nod]=low[nod]=timer;
st.push(nod);
inStack[nod]=true;
for (int u: graf[nod])
{
if (disc[u]==0)//daca nu l-am bagat inca
{
dfs(u);
low[nod]=min(low[nod], low[u]);
}
else if (inStack[u])
{
low[nod]=min(low[nod], disc[u]);
}
}
if (low[nod]==disc[nod])
{
cnt++;
while (true)
{
int nd=st.top();
st.pop();
inStack[nd]=false;
rez[cnt].push_back(nd);
if (nd==nod)
{
break;
}
}
}
}
int main()
{
fin>>n>>m;
for (int i=1; i<=m; i++)
{
fin>>a>>b;
graf[a].push_back(b);
}
for (int i=1; i<=n; i++)
{
if (disc[i]==0)
{
dfs(i);
}
}
fout<<cnt<<'\n';
for (int i=1; i<=cnt; i++)
{
sort(rez[i].begin(), rez[i].end());
for (auto u: rez[i])
{
fout<<u<<" ";
}
fout<<'\n';
}
return 0;
}