Pagini recente » Cod sursa (job #1865830) | Cod sursa (job #1640537) | Cod sursa (job #135524) | Cod sursa (job #1682293) | Cod sursa (job #1733289)
#include <cstdio>
#include <vector>
#include <stack>
#include <utility>
#include <bitset>
using namespace std;
int n, m;
vector<int> vecini[100100];
vector<int> vecinix[100100];
bitset<100100> viz;
bitset<100100> vizx;
int nr = 0;
vector<vector<int> > componente;
stack<int> st;
void citire()
{
scanf("%d %d", &n, &m);
int tmp1, tmp2;
for(int i = 0; i < m; i++)
{
scanf("%d %d", &tmp1, &tmp2);
tmp1--;
tmp2--;
vecini[tmp1].push_back(tmp2);
vecinix[tmp2].push_back(tmp1);
}
}
void dfs(int x)
{
int l = vecini[x].size();
viz[x] = true;
for(int i = 0; i < l; i++)
{
if(viz[vecini[x][i]] == false)
{
dfs(vecini[x][i]);
}
}
st.push(x);
}
void dfsx(int x)
{
componente[nr].push_back(x);
int l = vecinix[x].size();
vizx[x] = true;
for(int i = 0; i < l; i++)
{
if(vizx[vecinix[x][i]] == false)
{
dfsx(vecinix[x][i]);
}
}
}
void ctc()
{
for(int i = 0; i < n; i++)
{
if(viz[i] == false)
{
dfs(i);
}
}
while(!st.empty())
{
int x = st.top();
st.pop();
if(vizx[x] == false)
{
componente.push_back(vector<int>());
dfsx(x);
nr++;
}
}
}
void afisare()
{
printf("%d\n", nr);
for(int i = 0; i < nr; i++)
{
for(int j = 0; j < componente[i].size(); j++)
{
printf("%d ", componente[i][j] + 1);
}
printf("\n");
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
citire();
ctc();
afisare();
return 0;
}