Pagini recente » Cod sursa (job #1379288) | Cod sursa (job #1654036) | Cod sursa (job #2799248) | Cod sursa (job #2586016) | Cod sursa (job #2510299)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n, m, i, j, a, b, nrc, x, y;
int viz[100001], low[100001];
vector <int> cc[100001];
bool s[100001];
vector <int> g[100001];
stack <int> st;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int niv;
void dfs (int nod)
{
niv++;
viz[nod]=niv;
low[nod]=niv;
st.push(nod);
s[nod]=1;
for (int i=0;i<g[nod].size();i++) {
int fiu = g[nod][i];
if (viz[fiu]==0) {
dfs(fiu);
low[nod]=min(low[nod], low[fiu]);
}
else if (s[fiu]==1)
low[nod]=min(low[nod], viz[fiu]);
}
if (low[nod]==viz[nod]) {
nrc++;
x=nod;
do{
y=st.top();
s[y]=0;
cc[nrc].push_back(y);
st.pop();
}while(y!=x);
}
}
int main () {
fin>>n>>m;
for (i=1;i<=m;i++) {
fin>>a>>b;
g[a].push_back(b);
}
for (i=1;i<=n;i++) {
if (viz[i]==0){
niv=1;
dfs(i);
}
}
fout<<nrc<<"\n";
for (i=1;i<=nrc;i++) {
for (j=0;j<cc[i].size();j++)
fout<<cc[i][j]<<" ";
fout<<"\n";
}
return 0;
}